leetcode 热题 100

发表于 更新于 分类于

leetcode 热题 100

C/C++ 版本

[TOC]

双指针

11. 盛最多水的容器【双指针】

img
思路：
  好久没写代码了，加上之前写的双指针并不多。我对双指针比较刻板的印象一直是两层for循环i，j，初始时i,j都位于左界附近，但是对于第i次的内层循环，j只需要从第i-1次内层循环停下时的j开始循环，即内层的循环变量j一直在增加，而不会减少，故双指针复杂度O(n)。
  然鹅，本题利用双指针l,r，初始分别位于左界和右界，之后++l和--r,这样子移动。
  至于如何移动，写出容器容量公式便很容易想出V=(r - l - 1) * min(height[l], height[r])。为取得Vmax,考虑无论移动l or r,都会使得宽d = r - l - 1变小，故考虑如何使得min(height[l], height[r])变大，容易发现应该移动height小的那一个。
AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int l = 0, r = n - 1;
        int s = (r - l) * min(height[l], height[r]);
        int res = s;
        while(l < r)
        {
            if(height[l] < height[r]) ++l;
            else --r;
            s = (r - l) * min(height[l], height[r]);
            res = max(res, s);
        }
        return res;
    }
};

15. 三数之和【双指针】

img
思路：
  与上一题类似。
  先排序，之后搜一遍。
  对于nums[i],需要从右边找出两个数字使得和为-nums[i]。
  双指针l,r初始分别为左界和右界，据nums[l] + nums[r]与-nums[i]的大小关系决定移动哪个指针即可。
  另外对于去重，可直接通过set逃课。
AC代码

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        set<vector<int>> st;
        sort(nums.begin(), nums.end());

        int a, sum, last = -5000000;
        int l, r;
        bool flag;
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] == last) continue;
            else
            {
                last = nums[i];
                l = i + 1; 
                r = n - 1;
                a = -nums[i];
                while(l < r)
                {
                    sum = nums[l] + nums[r];
                    if(sum > a) --r;
                    else if(sum < a) ++l;
                    else 
                    {
                        vector<int> vt;
                        vt.push_back(nums[i]);
                        vt.push_back(nums[l]);
                        vt.push_back(nums[r]);
                        st.insert(vt);
                        ++l;
                    }
                }
            }
        }
        for(auto x : st) res.push_back(x);
        return res;
    }
};

Updated on 2024_12_03

分析：

  去重方面不使用set逃课。主要有两点，对于第一个元素，如果当前第一个元素等于前一个元素，那么直接continue，这涉及到一个子集的问题。第二点就是对于第二个元素，即将答案放入之后，左指针的移动，不能只移动一位，要移动到右侧第一个不等于当前这次答案里的第二个元素的那个点上。

AC代码：

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        const int inf = 0x3f3f3f3f;

        int x, y, l, r, last;
        for(int i = 0; i < n; ++i)
        {
            if(i != 0 && nums[i] == nums[i - 1]) continue;
            x = nums[i];
            y = -nums[i];
            l = i + 1;
            r = n - 1;
            last = inf;

            while(l < r)
            {
                if(nums[l] + nums[r] == y) 
                {
                    ans.push_back({nums[i], nums[l], nums[r]});
                    last = nums[l];
                    while(nums[++l] == last && l != n - 1) ;
                }
                else if(nums[l] + nums[r] < y) ++l;
                else --r;
            }
        }

        return ans;
    }
};

42. 接雨水【双指针/单调栈】

img
思路：
【解1】：预处理（对应官方题解dp解法）
  考虑每个洼地可容纳的雨水，取决于这个洼地左侧和右侧的最高的高地的较小值。对于每个洼地左侧和右侧的最高的高地，预处理即可。
【解2】：双指针
  思路同解1，只不过不做预处理，而是用双指针l,r初始分别为左界右界，移动过程中，分别维护扫过区域的最大值，每次移动最大值较小的那一侧，然后判断移动之后是洼地还是高地，洼地则计算接的雨水，高地则更新单侧最大值。
  关于为什么移动最大值较小的那一侧，假设较高的一侧是r。
  移动r侧，由于移动之后可能是高地or洼地，对于高地，不计算贡献，其实无所谓，但是对于洼地，需要计算贡献，此时贡献取决于洼地两侧最高的高地的较小值，然而左侧最高的高地其实是不确定的，故无法计算。倘若移动是l的一侧，虽然右侧最高的高地也是不确定的，但至少可以确定的是右侧的高地一定比左侧的高，故可以计算正确的贡献。
【解3】：单调栈
  构造一个单减栈（栈底>栈顶）。对于单调栈，其实每个元素都会进栈一次。
  对于遍历到的当前元素，若＜栈顶元素，入栈
  否则，说明存在可以积水的洼地，此时需要弹出栈顶元素，可积的雨水取决于洼地的宽度（据两侧高地的距离）及可积雨水的高地，循环处理，直至当前元素可以入栈。（此过程官方视频题解动画容易理解)。

AC代码：
预处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int trap(vector<int>& height) {
        
        int n = height.size();
        vector<int> rmx(n, 0);
        rmx[n - 1] = height[n - 1];

        for(int i = n - 2; i >= 0; --i) rmx[i] = max(height[i], rmx[i + 1]);
        int lmx = height[0], ans = 0;
        for(int i = 1; i < n - 1; ++i)
        {
            ans += max(min(lmx, rmx[i + 1]) - height[i], 0);
            lmx = max(lmx, height[i]);
        }

        return ans;
    }
};

双指针：

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
class Solution {
public:
    int trap(vector<int>& height) {
        
        int n = height.size();
        int res = 0;
        int l = 0, r = n - 1;
        int lmx = height[0], rmx = height[n - 1];
        
        while(l < r)
        {
            if(lmx < rmx)
            {
                ++l;
                if(lmx > height[l]) res += lmx - height[l];
                else lmx = height[l];
            }
            else
            {
                --r;
                if(rmx > height[r]) res += rmx - height[r];
                else rmx = height[r];
            }
        }

        return res;
    }
};

单调栈：

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
class Solution {
public:
    int trap(vector<int>& height) {
        
        stack<int> st;
        int n = height.size();
        int res = 0;
        
        for(int i = 0; i < n; ++i)
        {
            while(!st.empty() && height[i] > height[st.top()])
            {
                int tp = st.top();
                st.pop();
                if(st.empty()) break;
                int l = st.top();
                int d = i - l - 1;
                int h = min(height[l], height[i]) - height[tp];
                res += d * h;
            }
            st.push(i);
        }

        return res;
    }
};

子串

76. 最小覆盖子串【双指针/滑动窗口】

img
思路：
  先找出左边界为字符串s的左边界且能覆盖t的最小子串。
  之后，利用双指针/滑动窗口的思想，交替移动左右指针l,r
  具体规则如下：
  若当前子串能够覆盖，则++l,否则++r,每次移动后判断新的子串是否能够覆盖并且是否变小，保存最小能覆盖的子串长度以及其左右边界l,r。
  关于如何判断，只需在移动的过程中维护好如下容器or变量便显而易见。

1
2
3
4
5
6
map<char, int> mp; 			  //hash,'a'~'z'对应1~26,'A'~'Z'对应27~52
int cnt_s[64]				  //cnt_s[i]表示当前子串s[l~r]中i对应的字母个数，cnt_t[i]表示
int cnt_t[64];				  //cnt_t[i]表示t串中i对应的字母一共有几个
int num = 0, cnt = 0;		  //num表示t串一共有多少个不同的字母，cnt表示当前子串s[l~r]已经覆盖了t中的字母个数
int l, r;					  //当前正在处理的子串s[l~r]
int min_l, min_r, mi = inf;   //目前所有处理的子串中能覆盖的最小子串的左右边界及长度

AC代码：

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
class Solution {
public:
    string minWindow(string s, string t) {

        const int inf = 0x3f3f3f3f;
        int len1 = s.size(), len2 = t.size();
        map<char, int> mp;
        int cnt_s[64], cnt_t[64];
        int num = 0, cnt = 0;
        int l, r, min_l = 0, min_r = 0, mi = inf; 
        string str;
        
        for(char ch = 'a'; ch <= 'z'; ++ch) mp[ch] = ch - 'a' + 1;
        for(char ch = 'A'; ch <= 'Z'; ++ch) mp[ch] = ch - 'A' + 1 + 26;

        for(int i = 0; i < len2; ++i) ++cnt_t[mp[t[i]]];
        for(int i = 1; i < 55; ++i) if(cnt_t[i]) ++num;
        
        l = 0, r = -1;
        while(r < len1)
        {
            if(cnt == num)
            {
                if(cnt_s[mp[s[l]]] == cnt_t[mp[s[l]]]) --cnt;
                --cnt_s[mp[s[l++]]];
            }
            else
            {
                ++cnt_s[mp[s[++r]]];
                if(cnt_s[mp[s[r]]] == cnt_t[mp[s[r]]]) ++cnt;
            }

            if(cnt == num && r - l + 1 < mi)
            {
                mi = r - l + 1;
                min_l = l, min_r = r;
            } 
        }

        if(mi == inf) return "";
        else 
        {
            str = s.substr(min_l, mi);
            return str;
        }
    }
};

普通数组

189. 轮转数组【数论/gcd】

img
思路
  给出空间O(1)，且不用reverse的方法。（官方题解推导比较清楚）。
  维护两个变量pos和tmp,分别表示现在的位置和对应位置上的值，由此，更新只需pos = (pos + k) % n,swap(nums[pos], tmp),当pos回到最开始的位置时，我们称这是完成了一趟修改，此时应该停下，然鹅有的元素并没有遍历到。（只将下标为gcd(k,n)的倍数的元素遍历了，可证，另见类似题目，2015ICPC沈阳，跳青蛙🐸容斥），故需要将pos+1,再依次为开始，继续上述操作，直至回到开始位置并遍历全部位置。
  接下来考虑需要几趟（根据上面结论，其实可知需要gcd(n,k）趟)。假设转了a圈，遍历了b个元素,则an=bk,故an一定是n,k的倍数，又因为我们在第一次回到起点时便结束了，故a应尽可能的小，由此an=lcm(n,k),故b=lcm(n,k)/k,即需要遍历的趟数cnt=n/b=gcd(n,k)。
AC代码：

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
class Solution {
public:

    int gcd(int a, int b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }

    void rotate(vector<int>& nums, int k) {
    
        int n = nums.size();
        k %= n;
        int cnt = gcd(n, k);

        for(int i = 0; i < cnt; ++i)
        {
            int pos = i;
            int tmp = nums[i];
            while(true)
            {
                pos = (pos + k) % n;
                swap(nums[pos], tmp);
                if(pos == i) break;
            }
        }
    }
};

41. 缺失的第一个正数【置换/原地哈希】

img
思路：
【方法1】：置换（类似于上一个题目)

  • 对nums[i]<=0||nums[i]>n的元素统一处理。（设置为较大值或数组中出现过的某个1~n的值）。
  • 对于x = nums[i]，考虑swap(nums[i], nums[x-1])，即将nums[i]放到他应该在的位置上，如此循环下去，但是注意到当nums[i] == nums[x-1]时会进入死循环。
  • 所有1~n之间的数字都应当被放到对应的位置上，故最后遍历一遍数组，找到第一个不在对应位置之上的元素，便可知答案。
    【方法2】：改进开bool型数组，需要空间复杂度O(n)，原始数组nums同时充当bool数组（原地哈希）
    首先，给出开bool数组的方法，开一个大小为n+5的bool数组flag,flag[i]=true表示i出现，为此只需要找第一个flag[i]==false的i即可。
    改进方法如下：
  • 同方法1。
  • 通过第一步nums数组中应当只有正数。此时，对于一个1~n之间的数字x，我们就将nums[x - 1]中的元素修改为-nums[x - 1]（主要不要多次修改，以防负负得正）。即nums数组中元素的正负代表上述bool型数组的true和false,绝对值代表对应元素的值。
  • 与方法1类似。

AC代码：
【方法1】：置换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int firstMissingPositive(vector<int>& nums)
    {
        int n = nums.size();
        
        for(int i = 0; i < n; ++i) 
            while(nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) 
                swap(nums[i], nums[nums[i] - 1]);
       
       for(int i = 0; i < n; ++i) if(nums[i] != i + 1) return i + 1;
       
       return n + 1;
    }
};

【方法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
class Solution {
public:
    int firstMissingPositive(vector<int>& nums)
    {
        int n = nums.size();
        int x;

        bool flag = false;
        for(auto x: nums) if(x == 1) flag = true;
        if(!flag) return 1;

        for(int i = 0; i < n; ++i) if(nums[i] <= 0 || nums[i] > n) nums[i] = 1;

        for(int i = 0; i < n; ++i)
        {
            x = abs(nums[i]) - 1;
            nums[x] = -abs(nums[x]);
        }

        for(int i = 0; i < n; ++i) if(nums[i] > 0) return i + 1;

        return n + 1;
    }

};

矩阵

73. 矩阵置零【原地/随机】

img
思路：
【方法1】：原地
  比较容易想到，开一个长度为n和长度为m的bool型数组，分别表示第i行和第j列是否有0。这样空间复杂度O(n+m)。优化方法是用原数组的第一行和第一列充当这个bool数组。
用两个bool型变量col和row表示第1列,第1行是否有0,之后对于matrix[i][j]==0,将matrix[i][0]和matrix[0][i]标记为0
【方法2】：随机
  这个问题的关键是，只会把一开始就有的0所在的行和列全部置为0,后来的出现0不会操作。容易想到的一个思路就是先把有0的行和列中不是0的数字置为一个奇怪的数字（比如inf或是-inf），最后再把这些数改为0，但是发现取值为int的最小值到最大值，所以不行。但是n,m最大为200,随机生成的一个int在矩阵中出现的概率极低，故我们随机生成一个数字作为上述中的奇怪数字即可。（当然是需要判断的，如果运气不好，随机生成的数字正好出现了，就再随机生成一个)

AC代码：
【方法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
class Solution {
public:

    void setZeroes(vector<vector<int>>& matrix) {

        int n = matrix.size();
        int m = matrix[0].size();
        bool col = false, row = false; //column = 列，row = 行
        
        for(int i = 0; i < n; ++i)
        {
            if(!matrix[i][0])
            {
                col = true;
                break;
            }
        }

        for(int i = 0; i < m; ++i)
        {
            if(!matrix[0][i])
            {
                row = true;
                break;
            }
        }

        for(int i = 1; i < n; ++i)
        {
            for(int j = 1; j < m; ++j)
            {
                if(!matrix[i][j]) matrix[i][0] = matrix[0][j] = 0;
            }
        }

        for(int i = 1; i < n; ++i)
        {
            for(int j = 1; j < m; ++j)
            {
                if(!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0; 
            }
        }

        if(col) for(int i = 0; i < n; ++i) matrix[i][0] = 0;
        if(row) for(int i = 0; i < m; ++i) matrix[0][i] = 0;
    }
};

【方法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
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
class Solution {
public:

    int st_rand(vector<vector<int>>& matrix)
    {
        int xx = matrix.size();
        int yy = matrix[0].size();
        srand(time(NULL));
        int st;
        bool flag;
        while(true)
        {
            st = rand();
            flag = false;
            for(int i = 0; i < xx; ++i)
            {
                for(int j = 0; j < yy; ++j)
                {
                    if(matrix[i][j] == st) 
                    {
                        flag = true;
                        break;
                    }
                }
                if(flag) break;
            }
            return st;
        }
    }

    void work(vector<vector<int>>& matrix, int x, int y, int st)
    {
        int xx = matrix.size();
        int yy = matrix[0].size();
        for(int i = 0; i < xx; ++i) if(matrix[i][y] != 0) matrix[i][y] = st;
        for(int i = 0; i < yy; ++i) if(matrix[x][i] != 0) matrix[x][i] = st;
    }

    void setZeroes(vector<vector<int>>& matrix) {

        int xx = matrix.size();
        int yy = matrix[0].size();
  
        int st = st_rand(matrix);
        for(int i = 0; i < xx; ++i)
        {
            for(int j = 0; j < yy; ++j)
            {
                if(matrix[i][j] == 0) work(matrix, i, j, st);
            }
        }

        for(int i = 0; i < xx; ++i)
        {
            for(int j = 0; j < yy; ++j)
            {
                if(matrix[i][j] == st) matrix[i][j] = 0;
            }
        }

    }
};

48.旋转图像【mid】【数学公式推导】

分析：

  关键在于如何原地实现，数学公式推导是重点。官方题解很详细。

  官方题解方法二原地旋转是重点。

image-20241022002550562

  以及与方法三相关的各种翻转方法。（本质还是方法二中的公式）

image-20241022002707156

AC代码：

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
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        
        int n = matrix.size();
        int m = n / 2;

        int row, col, n_row, n_col, tmp, temp;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < m; ++j)
            {
                row = i, col = j;
                tmp = matrix[row][col];
                for(int k = 0; k < 4; ++k)
                {
                    n_row = col, n_col = n - row - 1;
                 
                    temp = matrix[n_row][n_col];
                    matrix[n_row][n_col] = tmp;
                    tmp = temp;
                    row = n_row;
                    col = n_col;
                }
            }
        }

        if(n&1) 
        {
            for(int i = 0; i < m; ++i)
            {
                row = m, col = i;
                tmp = matrix[row][col];
                for(int k = 0; k < 4; ++k)
                {
                    n_row = col, n_col = n - row - 1;
                
                    temp = matrix[n_row][n_col];
                    matrix[n_row][n_col] = tmp;
                    tmp = temp;
                    row = n_row;
                    col = n_col;
                }
            }

        }
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//先按行翻转，再副对角线翻转
//主对角线翻转（x，y）->(y,x)
//副（x，y）->(n−1−y,n−1−x)
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        
        int n = matrix.size();
        int m = n / 2;
        
        for(int i = 0; i < n; ++i) reverse(matrix[i].begin(), matrix[i].end());
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n - i; ++j) 
                swap(matrix[i][j], matrix[n - 1 - j][n - 1 - i]);
        }
        
    }
};

240.搜索二维矩阵 II【mid】【遍历】

分析：

  根据矩阵的性质，从右上角开始遍历。若右上角元素小于target，说明当前这一行都不可能是答案，若大于则当前一列都不可能是。复杂度O(m+n)。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        
        int n = matrix.size();
        int m = matrix[0].size();
        int i = 0, j = m - 1;
        
        while(i < n && j >= 0)
        {
            if(matrix[i][j] == target) return true;
            else if(matrix[i][j] < target) ++i;
            else --j;
        }

        return false;
    }
};

链表

234.回文链表【easy】【快慢指针】【O(1)空间】【链表反转】

分析：

  先用快慢指针寻找链表的中间结点。然后反转链表后半部分，之后遍历两个链表即可。

  快慢指针：快指针一次跳两个节点，慢指针一次跳一个节点。

  找中间节点和反转链表这两部分的函数感觉可以当模板。

AC代码：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* findMid(ListNode* head)
    {
        ListNode* fast = head;
        ListNode* slow = head;

        while(fast != nullptr)
        {
            fast = fast->next;
            if(fast != nullptr) fast = fast->next;
            slow = slow->next; 
        }

        return slow;
    }

    ListNode* reverseList(ListNode* head)
    {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* nextTemp = nullptr;

        while(cur != nullptr)
        {
            nextTemp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nextTemp;
        }

        return pre;
    }
    
    bool isPalindrome(ListNode* head) {
        
        if(head == nullptr) return true;

        ListNode* midNode = findMid(head);
        midNode = reverseList(midNode);

        ListNode* p1 = head;
        ListNode* p2 = midNode;

        while(p2 != nullptr)
        {
            if(p1->val != p2->val) return false;
            p1 = p1->next;
            p2 = p2->next;
        }

        return true;
    }
};

142.环形链表 II【mid】【快慢指针】【数学推导】

  好难的题。占位符，以后再写。

21.合并两个有序链表【easy】【递归】

分析：

  easy的难度，但是哥们写的不太顺利呀。方法一，直接递归，想一下这个问题的子问题，你就会发现这个问题很符合递归。方法二，迭代，记得定义一个头节点，会方便处理很多。

AC代码：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        
        if(list1 == nullptr) return list2;
        else if(list2 == nullptr) return list1;
        else if(list1->val <= list2->val) 
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        
        ListNode* head = new ListNode(-1);

        ListNode* pre = head;
        while(list1 != nullptr && list2 != nullptr)
        {
            if(list1->val <= list2->val)
            {
                pre->next = list1;
                list1 = list1->next;
            }
            else
            {
                pre->next = list2;
                list2 = list2->next;
            }
            pre = pre->next;
        }

        pre->next = list1 == nullptr ? list2 : list1;

        return head->next;
    }
};

2.两数相加【mid】【递归】

分析:

  又是一个很符合递归特征的题目。递归+迭代两种解法。

AC代码:

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry = 0) {
        
        if(l1 == nullptr && l2 == nullptr) return carry ? new ListNode(carry) : nullptr;
        
        if(l1 == nullptr) swap(l1, l2);
        
        int sum = carry + l1->val + (l2 ? l2->val : 0);
        l1->val = sum % 10;
        l1->next = addTwoNumbers(l1->next, (l2 ? l2->next : nullptr), sum / 10);
        
        return l1;
    }
};
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
        ListNode head;
        ListNode* cur = &head;
        int carry = 0;

        while(l1 || l2 || carry)
        {
            if(l1) 
            {
                carry += l1->val;
                l1 = l1->next;
            }
            if(l2)
            {
                carry += l2->val;
                l2 = l2->next;
            }
            cur = cur->next = new ListNode(carry % 10);
            carry /= 10;
        }

        return head.next;

    }
};

19.删除链表的倒数第 N 个结点【前后指针】

分析：

  前指针在后指针的前面n个节点即可。然后同时向前移动，这样前指针到链表尾的时候，后指针的next正好书倒数第N个节点，但是有个问题就是前后指针其实横跨了n+1个节点。所以，如果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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        
        ListNode dummy{0, head};
        ListNode* left = &dummy;
        ListNode* right = &dummy;
        
        while(n--) right = right -> next;
        
        while(right->next != nullptr)
        {
            left = left->next;
            right = right->next;
        }

        ListNode* nxt = left->next;
        left->next = left->next->next;
        delete nxt;

        return dummy.next;
    }
};

24.两两交换链表中的节点【反转链表】【哨兵】

分析：

img

  如图，需要反转的是p1和p2，维护好这四个变量即可。

AC代码：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        
        ListNode dummy{0, head};

        ListNode* p0 = &dummy;
        ListNode* p1 = head;
        ListNode* p2 = nullptr;
        ListNode* p3 = nullptr;

        while(p1 != nullptr && p1->next != nullptr)
        {
            p2 = p1->next;
            p3 = p2->next;

            p2->next = p1;
            p0->next = p2;
            p1->next = p3;

            p0 = p1;
            p1 = p3;
        }

        return dummy.next;
    }
};

138.随机链表的复制【链表深拷贝】

分析：

  单纯只考虑next指针，不考虑random指针，如下图。

img

AC代码：

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        
        Node* p = head;

        while(p)
        {
            Node* copy = new Node(p->val);
            copy->next = p->next;
            p->next = copy;
            p = copy->next;
        }

        p = head;
        while(p)
        {
            if(p->random) p->next->random = p->random->next;
            p = p->next->next;
        }

        Node* dummy = new Node(0);
        Node* q = dummy;
        p = head;

        while(p)
        {
            q->next = p->next;
            q = q->next;
            p->next = q->next;
            p = p->next;
        }

        return dummy->next;

    }
};

148.排序链表【链表排序】【归并排序】【分治】

分析：

  归并排序。

AC代码：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        
        ListNode* mid = findmid(head);
        ListNode* left = sortList(head);
        ListNode* right = sortList(mid);
        
        return merge(left, right);
    }
    
private:
    ListNode* findmid(ListNode* head)
    {
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast != nullptr && fast->next != nullptr) 
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        ListNode* mid = slow->next;
        slow->next = nullptr;
        return mid;
    }
    
    ListNode* merge(ListNode* l1, ListNode* l2) 
    {
        ListNode dummy(0); 
        ListNode* tail = &dummy;
        
        while (l1 != nullptr && l2 != nullptr) 
        {
            if (l1->val < l2->val) 
            {
                tail->next = l1;
                l1 = l1->next;
            } 
            else 
            {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        
        if (l1 != nullptr) tail->next = l1;
        else tail->next = l2;
        
        return dummy.next;
    }
};

23. 合并 K 个升序链表【归并排序】【分治】

分析：

  归并排序。

AC代码：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        
        int k = lists.size();
        if(k == 0) return nullptr;
        if(k == 1) return lists[0];

        int mid = (k + 1) / 2;
        ListNode* left = sortList(lists, 0, mid - 1);
        ListNode* right = sortList(lists, mid, k - 1);

        return merge(left, right);
    }

private:
    ListNode* sortList(vector<ListNode*>& lists, int l, int r)
    {
        if(l == r) return lists[l];

        int mid = (l + r) / 2;
        ListNode* left = sortList(lists, l, mid);
        ListNode* right = sortList(lists, mid + 1, r);

        return merge(left, right);
    }

    ListNode* merge(ListNode* l1, ListNode* l2)
    {
        ListNode dummy{0};
        ListNode* tail = &dummy;

        while(l1 != nullptr && l2 != nullptr)
        {
            if(l1->val < l2->val)
            {
                tail->next = l1;
                l1 = l1->next;
            }
            else 
            {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }

        if(l1 != nullptr) tail->next = l1;
        else tail->next = l2;

        return dummy.next;
    }
};

146. LRU 缓存【LRU】【哨兵】【双向链表】

分析：

  idea from here。取书，放书的比喻很形象。

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
// 节点类，双向链表
class Node{
public:
    int key;
    int value;
    Node* pre;
    Node* nxt;

    Node(int k = 0, int v = 0) : key(k), value(v) {}
};

// LRU缓存类
class LRUCache {
private:
    int cap;
    Node* dummy;
    unordered_map<int, Node*> key_to_node;

    void remove(Node* x); 	    // 从双向链表移除节点
    void push_front(Node* x);	// 把节点加入到双向链表头
    Node* get_node(int key); 	// 获取双向链表中关键字为key的节点，如果存在，会把这个节点放到链表头

public:
    LRUCache(int capacity) : cap(capacity), dummy(new Node()) {}
    
    int get(int key);	// 获取key对应的value		
    
    void put(int key, int value);	// 新增关键字key
};

AC代码：

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
class Node{
public:
    int key;
    int value;
    Node* pre;
    Node* nxt;

    Node(int k = 0, int v = 0) : key(k), value(v) {}
};

class LRUCache {
private:
    int cap;
    Node* dummy;
    unordered_map<int, Node*> key_to_node;

    void remove(Node* x)
    {
        x->pre->nxt = x->nxt;
        x->nxt->pre = x->pre;
    }

    void push_front(Node* x)
    {
        x->pre = dummy;
        x->nxt = dummy->nxt;
        x->pre->nxt = x;
        x->nxt->pre = x;
    }

    Node* get_node(int key)
    {
        auto it = key_to_node.find(key);
        if(it == key_to_node.end()) return nullptr;

        Node* node = it->second;
        remove(node);
        push_front(node);
        return node;
    }
    

public:
    LRUCache(int capacity) : cap(capacity), dummy(new Node()) {
        dummy->pre = dummy;
        dummy->nxt = dummy;
    }
    
    int get(int key) {
        Node* node = get_node(key);
        return node ? node->value : -1;
    }
    
    void put(int key, int value) {
        
        Node* node = get_node(key);
        if(node) node->value = value;
        else
        {
            key_to_node[key] = node = new Node(key, value);
            push_front(node);
            if(key_to_node.size() > cap)
            {
                Node* back_node = dummy->pre;
                key_to_node.erase(back_node->key);
                remove(back_node);
                delete back_node;
            }
        }
    }
};