Posted on | Post modified: |
Words count in article: 2.6k

链表题

反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode* reverseList(ListNode* head) {
    // 三指针
    // ListNode *pre = head, *cur = nullptr;
    // while (pre) {
    //     ListNode* t = pre->next;
    //     pre->next = cur;
    //     cur = pre;
    //     pre = t;
    // }
    
    // return cur;

    // 递归
    if (!head || !head->next) return head;  // 结束条件，返回的是最后的头结点

    ListNode *res = reverseList(head->next); // 递归下一个节点，通过递归去寻找和保存下一个节点的指针
    head->next->next = head; // 将后面的倒过来指向自己
    head->next = nullptr;

    return res;
}

反转链表II

反转从位置m到n的链表，一趟扫描完成。

有哨兵和无哨兵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
ListNode* reverseBetween(ListNode *head, int m, int n) {
    if (!head) return head;
    int cnt = n - m + 1;

    ListNode *H = new ListNode();
    H->next = head;
    ListNode *dummy = H, *pre, *tail, *t;

    while (m > 1) {
        dummy = dummy->next;
        -- m;
    }

    pre = dummy->next;
    while (cnt --) {
        t = pre->next;
        pre->next = tail;
        tail = pre;
        pre = t;
    }

    dummy->next->next = pre;  // 有哨兵则不需要判断是否有第一段
    dummy->next = tail;

    return H->next;
    // // 除head外，还需rear和h来分别保存第一段的结尾和第二段的开头
    // ListNode *rear = nullptr,  *h;  // 用于保存边界
    // ListNode *pre = head, *cur;     // 用于反转链表
    // while (m > 1) {
    //     rear = pre;
    //     pre = pre->next;
    //     -- m;
    // }

    // h = pre;

    // // 反转
    // while (cnt --) {
    //     ListNode *t = pre->next;
    //     pre->next = cur;
    //     cur = pre;
    //     pre = t;
    // }

    // // 连接一二段
    // if (rear) rear->next = cur;  // 判断是否有第一段
    // else      head = cur;

    // h->next = pre;              // 连接第三段

    // return head;
}

k个一组翻转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode *H = new ListNode();
    H->next = head;
    ListNode *cur = H, *pre, *tail = nullptr, *t;   // cur是每k个链表段的表头节点, pre tail 用于翻转, t是中间临时指针

    while (cur->next) {
        pre = cur->next;
        for (int i = 0; i < k; ++ i) {  // 判断是否剩余k个
            if (!pre) return H->next;
            pre = pre->next;
        }

        pre = cur->next;                // 重新指向第一个节点，开始翻转
        for (int i = 0; i < k; ++ i) {  // 翻转k个
            t = pre->next;
            pre->next = tail;
            tail = pre;
            pre = t;
        }

        // 连接
        t = cur->next;     // 保存翻转前的第一个节点，也就是翻转后的尾节点
        t->next = pre;     // 新的尾节点 和 后一段的头节点 连接 
        cur->next = tail;  // 该段新的头结点

        cur = t;           // 翻转后的尾节点是下一段的头结点
    }

    return H->next;
}

分隔链表(快慢指针)

慢指针负责找到第一个 >= x 的节点的父节点，然后快指针负责从该节点开始寻找 < x 的节点，并将其插入到慢指针之后，同时慢指针指向插入的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
ListNode* partition(ListNode* head, int x) {
    ListNode *dummy = new ListNode(-1, head);
    ListNode *slow = dummy, *fast = slow;
    ListNode *t;
    while (fast->next) {
        if (slow->next->val < x) {  // 在找到第一个>= x的数后就不会再执行，之后fast指针找到的 < x 的数通过头插法加入
            slow = slow->next;
            fast = slow;            // fast指针的起始位置
        }else if (fast->next->val < x) { // 找寻的节点是next指向的节点满足 < x 的节点。
            t = fast->next;
            fast->next = t->next;
            t->next = slow->next;
            slow->next = t;
            slow = t;
        }else
            fast = fast->next;
    }

    // while (cur->next && cur->next->val < x) {
    //     cur = cur->next;
    // }

    // ListNode *p = cur, *t;
    // while (p->next) {
    //     if (p->next->val < x) {
    //         t = p->next;
    //         p->next = t->next;
    //         t->next = cur->next;
    //         cur->next = t;
    //         cur = t;
    //     }else {
    //         p = p->next;
    //     }
    // }

    return dummy->next;
}

两个链表的第一个公共节点

环形链表

环形链表就是会访问到之前访问过的节点，可以通过hash表保存。若对空间有要求可以用快慢指针，这个需要推公式：

在有环的情况中，fast和slow相遇，最终的步数是f = 2s，设进入环之前有a个节点，环内有b个节点，a是它们都走过的路程，因此在环中相遇即f比s多走n个环，即 f = s + nb ，可推出s = nb ，这说明s走的路程是环b的整数倍，s在进入环前走了a个距离，那么从当前点再走a个距离便到了进入环的入口，因此再设一个从head出发 的节点，当它与相遇后的s再次相遇的节点就是环的入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 快慢指针
ListNode *detectCycle(ListNode *head)
{
    ListNode *fast = head, *slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            // 达到相遇点
            ListNode *slow2 = head;
            while (slow2 != slow)
            {
                slow2 = slow2->next;
                slow = slow->next;
            }
            return slow2;
        }
    }
    return nullptr;
}

双指针

三数之和

求满足三数之和为0，且不重复的组合

这题的一个关键是不重复，和为0。暴力的做法是三重循环得到满足和为0的组合，再用哈希表去重。优化去重可先将它们排序后再循环，此时三个数$a, b, c$满足$a \le b \le c$ 。这样元素的组合顺序就确定了，但是没有完全去除重复，例如$-2, 2,2,2$ ，$b,c$可以两次都取2，因此在得到一个组合后，需要判断当前的循环的下一个数是否跟本次加入组合的数相同，相同则跳过。这样就可以完全去除重复。

再观察到$a \le b \le c$ ，后面两个数的大小关系是确定的，因此可以分别从左右两侧进行第二第三层循环，在它们相交时终止，这样将复杂度降到$O(N^2)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<vector<int>> threeSum(vector<int>& nums) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    vector<vector<int> > res;

    for (int p = 0; p < n - 2; ++ p) {
        if (nums[p] > 0) return res;
        if (p > 0 && nums[p] == nums[p - 1]) continue;

        for (int l = p + 1, r = n - 1; l <  r; ) {
            int t = nums[p] + nums[l] + nums[r];
            if (t == 0) {
                res.push_back({nums[p], nums[l ++], nums[r --]});
                while (l < r && nums[l] == nums[l - 1]) ++ l;  // 与之前已加入的比较，是否重复
                while (l < r && nums[r] == nums[r + 1]) -- r;  
            }
            else if (t < 0) {
                ++ l;
            }
            else {
                -- r;
            }
        }
    }

    return res;
}

单调栈

下一个更大的数

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    stack<int> stk;
    vector<int> res(n, -1);

    // 5 4 3 2 7 前面四个单减的第一个最大的数都是7，因此不需要再多余的挨个搜索
    // 当单减的时候就入栈，直到遇到一个较大的数，这时查看这个数能大过多少栈中的，则为栈中的数赋值即可
    for (int i = 0; i < 2 * n - 1; ++ i) {
        while (stk.size() && nums[stk.top()] < nums[i % n]) {
            res[stk.top()] = nums[i % n];
            stk.pop();
        }
        stk.push(i % n);
    }

    return res;
}

 

思路

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// 暴力做法，直接搜索一个柱子两侧最高的柱，它的水平线一定是其中较矮的那个，这样每次左右分别搜索最高的柱子，一次搜索可以确定一个柱子上方的雨水量
// 搜索时需要包括本身（如果没有比自己高的那自己就是最高的）。
// class Solution{
// public:

// int trap(vector<int>& height)
// {
//     int ans = 0;
//     int size = height.size();
//     for (int i = 1; i < size - 1; i++) {
//         int max_left = 0, max_right = 0;
//         for (int j = i; j >= 0; j--) { //Search the left part for max bar size
//             max_left = max(max_left, height[j]);
//         }
//         for (int j = i; j < size; j++) { //Search the right part for max bar size
//             max_right = max(max_right, height[j]);
//         }
        
//         int t = min(max_left, max_right) - height[i];
//         ans += t;
//     }
//     return ans;
// }
// };


// // 动态规划：先正反两次遍历得到每个位置i的左右两端最大的数，则可以直接计算每个位置的水量
// class Solution {
// public:
//     int trap(vector<int>& h) {
//        int n = h.size();
//        int res = 0;

//        vector<int> left_max(n), right_max(n);
//        for (int t = -1, i = 0; i < n - 1; ++ i) {
//            if (t < h[i]) t = h[i];
//            left_max[i] = t; 
//        }

//        for (int t = -1, i = n - 1; i > 0; -- i) {
//            if (t < h[i]) t = h[i];
//            right_max[i] = t;
//        }

//        for (int i = 1; i < n - 1; ++ i) {
//            res += (min(right_max[i], left_max[i]) - h[i]);
//        }
//        return res;
//     }
// };

// 单调栈， 如果说暴力是按纵轴确认，单调栈就是按横轴确认（确定两个柱子之间有多宽的雨水量）。
// 雨水会出现在凹槽中，因此从左遍历只需要维护一个单调递减栈，就能保证左侧是凹的形状，当遇到不满足单调递减的柱时，计算左侧是否已有积水，和积水的宽度高度
// 并且由单调栈的性质，保存的一定是一个不增的序列。
// class Solution {
//     int stk[100000];
//     int tt = -1;
// public:
//     int trap(vector<int>& h) {
//         int n = h.size();
        
//         int res = 0;
//         for (int i = 0; i < n; ++ i) {
//             while (tt != -1 && h[stk[tt]] < h[i]) {
//                 int mid = stk[tt --];
//                 if (tt == -1) break;
//                 int l = stk[tt];
//                 res += (i - l - 1) * (min(h[i], h[l]) - h[mid]);
//             }
//             stk[++ tt] = i;
//         }
//         return res;
//     }
// };


// 双指针 ： 暴力法和动态规划都是需要一个柱子左右两侧最高的中较小的即可，那么可从两侧分别遍历，分别维护两侧最大的柱子，
// 在遍历的过程中，可以先计算较小端的水量，以左侧为例，它左侧的最大值已确定，而右侧最大值比它大，那么它的水量只与左侧最大值相关。
class Solution {
public:
    int trap(vector<int>& h) {
        int res = 0;
        int l = 0, r = h.size() - 1;
        int left_max = 0, right_max = 0;

        while (l <= r) {
            if (h[l] <= h[r]) {
                h[l] < left_max ? res += left_max - h[l] : left_max = h[l];
                ++ l;
            }else {
                h[r] < right_max ? res += right_max - h[r] : right_max = h[r];
                -- r;
            }
        }

        return res;
    }
};