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:
    vector<int> twoSum(vector<int>& numbers, int target) {
        // 法一：暴力做法  时间复杂度 O(n^2)
//        int i, j;
//        for (i = 0; i < numbers.size(); ++i)
//            for (j = 0; j < numbers.size(); ++j) {
//                if ((numbers[i]+numbers[j]) == target)
//                    break;
//            }
//        return {i, j};
        // 法二：双指针  时间复杂度 O(n)
        // 注意：这是 从下标1 开始的整数数组
        // [2, 7, 11, 15] target=9
        // 这里返回 2 7下标，从1开始就是返回 [1, 2]
        // 而数组下标默认从 0开始，故后面的返回值都要+1
        int i = 0, j = numbers.size()-1;
        // 由于题目给出了这个index范围1 <= index1 < index2 <= numbers.length，所以while循环可以退出条件可以写为如下：
        // 当然 由于题目保证：每个输入都有唯一答案，所以也可以写：while(true)
        while (i < j) {
            if (numbers[i] + numbers[j] > target) j--;
            else if (numbers[i] + numbers[j] < target) i++;
            else break;
        }
        return {i+1, j+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

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int i, j, k;
        vector<vector<int>> vi;
        // 枚举 nums[k]
        // 要使得：nums[i] + nums[j] + nums[k] = 0
        // 相当于：nums[i] + nums[j] = -nums[k]
        // 转换成两数之和，使用双向指针求解
        // 时间复杂度：O(n^2)
        // 这里有个边界情况：k > 2时，样例：nums = [0,0,0]
        // 由于判断不通过，不会进入循环，也就没有找出唯一解，为了解决这个问题，把k > 2改为 k>=2
        // 把 控制三个数不相等放在后面 if (i < j)中，由于 j初始化本来就比k 小1
        // 所以 只要限制if(i < j)即可达到：i < j < k 的效果
        for (k = nums.size()-1; k >= 2; k--) {
            i = 0, j = k-1;
            if (k < nums.size()-1 && nums[k] == nums[k+1]){
                // 由于每次在 for循环中都会改变 k值，所以这里直接continue，不用改变k值
                continue;
            }
            while (i < j) {
                if (i > 0 && nums[i] == nums[i-1]) {
                    i++; continue;
                }
                if (j < k-1 && nums[j] == nums[j+1]) {
                    j--; continue;
                }
                if(nums[i] + nums[j] < -nums[k]) i++;
                else if(nums[i] + nums[j] > -nums[k]) j--;
                // 注意这里由于不是限制说只有一个解，所以需要一直循环，把所有满足条件解都找到
                else {
//                    continue;
                    vi.push_back({nums[i], nums[j], nums[k]});
                    // 注意要改变一下 i, j的值，不然会死循环
                    i++; j--;
                }
            }
//            if (i < j)
//                vi.push_back({nums[i], nums[j], nums[k]});
        }
        return vi;
    }
};

 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

class Solution {
public:
      vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int i, j, k;
        vector<vector<int>> vi;
        for (k = nums.size()-1; k >= 2; k--) {
            i = 0, j = k-1;
            if (k < nums.size()-1 && nums[k] == nums[k+1]){
                // 由于每次在 for循环中都会改变 k值，所以这里直接continue，不用改变k值
                continue;
            }
            if (k >= 2 && nums[k]+nums[k-1]+nums[k-2]<0)
                break;
            if (k >= 2 && nums[i]+nums[i+1]+nums[k]>0)
                continue;
            while (i < j) {
                if(nums[i] + nums[j] < -nums[k]) i++;
                else if(nums[i] + nums[j] > -nums[k]) j--;
                    // 注意这里由于不是限制说只有一个解，所以需要一直循环，把所有满足条件解都找到
                else {
//                    continue;
                    vi.push_back({nums[i], nums[j], nums[k]});
                    // 注意要改变一下 i, j的值，不然会死循环
                    i++;
                    while(i < j && nums[i] == nums[i-1]) {
                        i++; // 这里找到一个符合的nums[i]了，执行过i++, i > 0一定成立
                    }
                    j--;
                    while(j > i && nums[j] == nums[j+1]) {
                        j--; // 这里找到一个符合的nums[j]了，执行过j--，j < k-1一定成立
                    }

                }
            }
        }
        return vi;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size()-1;
        int maxVal = 0;
        while (left < right) {
            maxVal = max(maxVal, min(height[left], height[right]) * (right - left));
            if (height[left] > height[right]) right--;
            else  left++;
        }
        return maxVal;
    }
    // 更加优雅写法
    int maxArea1(vector<int>& height) {
        int i = 0, j = height.size() - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j] ?
                  max(res, (j - i) * height[i++]):
                  max(res, (j - i) * height[j--]);
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9

    vector<int> pre_max;  // 创建两个数组，用于存储前缀最大值 和 后缀最大值
    pre_max.push_back(height[0]);
    int size = height.size();
    for (int i = 1; i < size; ++i)
        pre_max.push_back(max(pre_max[i-1], height[i]));
    vector<int> suf_max(size, 0);
    suf_max[size-1] = height[size-1];
    for (int i = size-2; i >= 0; --i)
        suf_max[i] = max(suf_max[i+1], height[i]);

 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

class Solution {
public:
    int trap(vector<int>& height) {
        int preMax = 0, sufMax = 0;
        int left = 0, right = height.size()-1;
        int ans = 0;
        // 双指针这里不需要等号吧，如果等于的时候还有容量，
        // 说明这个位置两边必定有大于该位置的数，那么在循环过程中就会先计算这个位置了
        // 不加等号也是可以的，最后必定会停在一个无法接水的位置。
        while (left <= right) {
            preMax = max(preMax, height[left]);
            sufMax = max(sufMax, height[right]);
            if (preMax < sufMax) {
                ans += preMax-height[left++];
            } else {
                ans += sufMax-height[right--];
            }
        }
        return ans;
    }
    int trap1(vector<int>& height) {
        vector<int> pre_max;  // 创建两个数组，用于存储前缀最大值 和 后缀最大值
        pre_max.push_back(height[0]);
        int size = height.size();
        for (int i = 1; i < size; ++i)
            pre_max.push_back(max(pre_max[i-1], height[i]));
        vector<int> suf_max(size, 0);
        suf_max[size-1] = height[size-1];
        for (int i = size-2; i >= 0; --i)
            suf_max[i] = max(suf_max[i+1], height[i]);
        int ans = 0;
        for (int i = 0; i < size-1; ++i)
            ans += (min(pre_max[i], suf_max[i]) - 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

class Solution {
public:
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)
    int minSubArrayLen(int target, vector<int>& nums) {
        int size = nums.size();
        int ans = size+1, left = 0;
        int sum = 0;
        for (int i = 0; i < size; ++i) {
            sum += nums[i];
            // 单调性：
            // 对于本题而言，left移动时，子数组的和是在不断变小的
            // while循环里边的条件不断变化，从满足要求——> 不满足要求
            // 只有满足了 单调性，才可以使用双指针
            while(sum >= target) {
                ans = min(ans, i - left + 1);
                sum -= nums[left];
                left += 1;
            }
        }
        return ans <= size ? ans : 0;
        // if (ans == size+1)
        //     return 0;
        // else
        //     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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        // 暴力解法：由于每次 right = left 指针回溯
        // 故时间复杂度为：O(n^2)
        int len = nums.size();
        int ans = 0;
        int product = 1;
        int left = 0, right = left;
        while (left < len) {
            while (right < len && product * nums[right] < k) {
                ans += 1;
                product *= nums[right];
                right++;
            }
            left++; right = left;
            product = 1;
        }
        return ans;
    }
    int numSubarrayProductLessThanK1(vector<int>& nums, int k) {
        // 固定右端点，从 0 开始拓展，用下标 right 表示，表示 以right 为结尾的子数组
        // 左端点默认从 0 开始
        // 这里需要使用前缀 成绩数组预处理一下 这样就需要开一个 n大小数组，空间复杂度过高
        // 从上面 由左到右 遍历的话，前缀乘积数组可以暂时 用一个sumProduct 暂存，这样就可以达到O(1)时间复杂度
        // 加速代码如下
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        if (k <= 1) return 0;  // 特判，防止 后面循环出错

        int len = nums.size();
        int ans = 0;
        int product = 1;
        int right = 0, left = 0;
        while (right < len) {
            product *= nums[right];
            // 这里循环 product >= k要保证 left <= right，前提是：k <= 1
            while (product >= k) {
                product /= nums[left++];
            }
            ans += (right - left + 1);
            right++;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int> mp;
        int ans = 0;
        int r = 0, l = 0;
        while (r < s.length()) {
            if (mp.count(s[r]) > 0)
                mp[s[r]] += 1;
            else mp[s[r]] = 1;
            while (mp[s[r]] > 1) {
                mp[s[l++]] -= 1;
            }
            ans = max(ans, r-l+1);
            // 注意 r++，否则会出现 死循环问题
            r++;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

		// 左闭右闭 区间写法
        // while循环条件为：left <= right
        std::function<int(vector<int>, int)> lower_bound = [&] (vector<int> nums, int target){
            int left = 0, right = nums.size()-1; // 闭区间[left, right]
            while (left <= right) { // 区间不为空
                // left + (right - left) / 2 这种写法可以防止整数溢出问题
                // 普通写法：mid = (left + right) / 2
                int mid = (left + right) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;  // [mid+1, right]
                } else {
                    right = mid - 1;  // [left, mid-1]
                }
            }
            return left;
        };

 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

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 左闭右闭 区间写法
        // while循环条件为：left <= right
        std::function<int(vector<int>, int)> lower_bound = [&] (vector<int> nums, int target){
            int left = 0, right = nums.size()-1; // 闭区间[left, right]
            while (left <= right) { // 区间不为空
                // left + (right - left) / 2 这种写法可以防止整数溢出问题
                // 普通写法：mid = (left + right) / 2
                int mid = (left + right) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;  // [mid+1, right]
                } else {
                    right = mid - 1;  // [left, mid-1]
                }
            }
            return left;
// No viable conversion from '(lambda at /mnt/g/CodeFile/CODE_CPP/Data-Structure/Basic/LC-BasicAlgorithm/34.在排序数组中查找元素的第一个和最后一个位置.cpp:13:60)' to 'std::function<int (vector<int>, int)>'
// 注意：一个函数没有 特定类型的返回值，lambda表达式会上面这个错误
//            return 1;

        };
        // 左闭右开 区间写法
        // while循环条件为：left < right
        std::function<int(vector<int>, int)> lower_bound2 = [&] (vector<int> nums, int target) {
            int left = 0, right = nums.size(); // 左闭右开 [left, right)
            while (left < right) { // 区间不为空
                // left + (right - left) / 2 这种写法可以防止整数溢出问题
                // 普通写法：mid = (left + right) / 2
                int mid = (left + right) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;  // [mid+1, right)
                } else {
                    right = mid;  // [left, mid)
                }
            }
            return left;
        };

        // 左开右开 区间写法
        // while循环条件为：left+1 < right
        std::function<int(vector<int>, int)> lower_bound3 = [&] (vector<int> nums, int target) {
            int left = -1, right = nums.size(); // 左开右开 (left, right)
            while (left+1 < right) { // 区间不为空
                // left + (right - left) / 2 这种写法可以防止整数溢出问题
                // 普通写法：mid = (left + right) / 2
                int mid = (left + right) / 2;
                if (nums[mid] < target) {
                    left = mid;  // (mid, right)
                } else {
                    right = mid;  // (left, mid)
                }
            }
            return left;
        };
        int start = lower_bound(nums, target);
        // 表明数组中 没有目标的等于 target的元素
        if(start == nums.size() || nums[start] != target)
            return {-1, -1};
        int end = lower_bound(nums, target + 1) - 1;
        // 如果说 start存在，则end一定会有解，直接返回即可
        return {start, end};

    }
    // 时间复杂度：取决于 lower_bound的复杂度，由于每次都是去掉数组的一半元素
    // 所以这里 数组不断减半，时间复杂度为O(logn)
};

 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 Solution {
public:
    // 疑问：右边界要初始成为n - 2（如果用闭区间的话），这个是怎么想到的呢？
    // 答：因为 n-1 要么是答案，要么在答案右侧，所以 n-1 一定是蓝色，无需二分。
    // 对于红蓝染色法 区间的说明：
    // 区间表示【不知道要染成红色还是蓝色】的下标组成的范围。
    // 如果区间内全为红色，那么答案自然就是 n-1。
    // 按照定义，n-1 要么是峰顶，要么在峰顶右侧，所以一定染成蓝色，自然就不需要在初始的区间内了。

    // 时间复杂度：O(logn)
    // 空间复杂度：O(1)
    int findPeakElement(vector<int>& nums) {
        // 二分范围：[0, n-2]
        // 开区间为：(-1, n-1)
        int left = -1, right = nums.size()-1;
        while (left + 1 < right) {
            int mid = left + (right - left)/2;
            if (nums[mid] > nums[mid+1]) // 蓝色
                right = mid;
            else
                left = mid;
        }
        // 这里说明为何要 return right
        // 看while循环中分支判断条件：
        //   只有 nums[mid] > nums[mid+1]的时候，将right更新为mid
        //   这里说明：right总是想着峰顶靠近，最后到达封顶的下标位置
        return right;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int findMin(vector<int>& nums) {
        // [0, n-2]
        // (-1, n-1)
        // 采用 左开右开 写法，注意初始化，刚刚初始化left = 0样例过不了了
        int left = -1, right = nums.size()-1;
        while (left+1 < right) {
            // int mid = left + (right - left) / 2;
            int mid = (left + right) / 2;
            if (nums[mid] < nums[nums.size()-1])
                right = mid;
            else
                left = mid;
        }
        // 返回 指针left 或者 right，得看情况
        // right改变分支时，判断语句是：nums[mid] < nums[nums.size()-1]
        // 这说明：mid 指向元素在 最小元素的右侧，或者就是最小元素
        // 等到循环停止时，right恰好指向的是最小元素，直接返回nums[right]
        return nums[right];
    }
};

 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

class Solution {
public:
    // 法一：结合上一题：寻找旋转排序数组中的最小值，一次二分找到最小值分界点
    // 然后接下来看 target在哪个升序区间范围内，再一次二分进行查找
    int search(vector<int>& nums, int target) {
        int left = -1, right = nums.size()-1;
        while (left+1 < right) {
            // int mid = left + (right - left) / 2;
            int mid = (left + right) / 2;
            if (nums[mid] < nums[nums.size()-1])
                right = mid;
            else
                left = mid;
        }
        if(target < nums[right]) return -1;
        int l, r;
        // target <= last，表明：target在数组中 第二段递增区间
        // target > last, 表明：target在数组中，第一段递增区间
        if(target <= nums[nums.size()-1]) {
            l = right, r = nums.size()-1;
        } else {
            // 这里的 l r初始化没有考虑到一下这种情况
            // nums = [1] ; target = 1
            // 考虑到的是 nums[right]左边还有 元素情况
            // 万一 nums[right]就是最小值，左边已经没有元素，就会因为没进入循环，误判
            // 添加特判样例
            // 或者 像上面的if判断语句修正：target < nums[nums.size()-1] => target <= nums[nums.size()-1]
            l = 0, r = right -1;
        }
        while(l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target)
                return mid;
            else if(nums[mid] < target) {
                l = mid+1;
            } else {
                r = mid-1;
            }
        }
        return -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

class Solution {
public:
    int search(vector<int>& nums, int target) {
        std::function<bool(int)> is_blue = [&] (int i) {
            int end = nums[nums.size()-1];
            if(nums[i] > end) {
                return target > end && nums[i] >= target;
            } else {
                return target > end || nums[i] >= target;
            }
        };

        int left = -1, right = nums.size();
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if(is_blue(mid))
                right = mid;
            else
                left = mid;
        }
        if(right == nums.size() || nums[right] != target)
            return -1;
        return right;
    }
};

 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

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* reverseList(ListNode* head) {
        // head = [1,2,3,4,5]
        // cout << head->val << endl;s
        // 输出：1
        if(head == nullptr)
            return head;
        ListNode *p = head->next, *q = nullptr;
        while(p) {
            head->next = q;
            q = head, head = p;
            p = p->next;
        }
        if(head) head->next = q;
        return head;
    }
    // 博主的思路
    // 执行用时：击败100% 用户
    ListNode* reverseList1(ListNode* head) {
        ListNode *pre = nullptr;
        ListNode *cur = head, *nxt = nullptr;
        while(cur) {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
};

 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

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* reverseBetween(ListNode* head, int left, int right) {
        // 初始化哨兵结点，next值指向 head
        ListNode *dummy = new ListNode(-1, head);
        ListNode *p0 = dummy;
        // p0指向要反转链表部分 第一个结点的上一个结点
        for(int i = 0; i < left-1; ++i)
            p0 = p0->next;

        ListNode *pre = nullptr;
        ListNode *cur = p0->next, *nxt = nullptr;
        int len = right - left + 1;
        for(int i = 0; i < len; ++i){
            nxt = cur->next;
            cur->next = pre; // 核心，每次反转修改的 指针指向
            pre = cur;
            cur = nxt;
        }
        p0->next->next = cur;
        p0->next = pre;

        // 若是返回head，当left=1，会被一下案例卡住测试
        // [3,5]
        // left=1, right=2
        // [5,3]
        // 故需要返回 dummy哨兵结点指向的下一个结点 (保证为链表的头结点)
        return dummy->next;
    }

 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

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* reverseKGroup(ListNode* head, int k) {
        int num = 0;
        ListNode *p = head;
        // 首先获取链表结点数 num
        while(p) {
            num++;
            p = p->next;
        }
        // 初始化哨兵结点，next值指向 head
        ListNode *dummy = new ListNode(-1, head);
        ListNode *p0 = dummy;

        // 这里 pre, cur, nxt指针初始化可以放在循环外部
        // 从内层循环分析，每次翻转K个结点之后，cur恰好指向下一组K个结点中第一个结点位置
        // nxt 在进入循环就 赋值给下一组K个结点的 下一个结点
        // pre虽然没有能每次都在 cur指向结点前一个结点，但是其初始值并不会影响什么
        // 一开始 将pre赋值给 第一个结点的next指针，后面翻转最后一步 第一个结点的Next指针也需要重新赋值
        // 所以没有任何影响
        ListNode *pre = nullptr;
        ListNode *cur = p0->next, *nxt = nullptr;
        while(num >= k) {
            num -= k;
            for(int i = 0; i < k; ++i){
                nxt = cur->next;
                cur->next = pre; // 核心，每次反转修改的 指针指向
                pre = cur;
                cur = nxt;
            }
            nxt = p0->next;
            p0->next->next = cur;
            p0->next = pre;
            p0 = nxt;
        }
 		// K个一组翻转链表之后， 哨兵结点dummy 的next还是指向头结点
        // 上面p0 一开始赋值就是哨兵结点，也有参与指针运算
        return dummy->next;
    }
};

 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

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* middleNode(ListNode* head) {
        ListNode *p = head;
        int len = 0;  // 由于最后p = nullptr才退出，从p = head到p = nullptr，一共经过结点个数就是长度
        while(p) {
            p = p->next;
            len++;
        }
        int mid = len / 2 + 1;
        p = head;
        for (int i = 2; i <= mid; ++i){
            p = p->next;
        }
        return p;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
       ListNode *slow = head, *fast = head;
       while(fast && fast->next){
           fast = fast->next->next;
           slow = slow->next;
       }
       return slow;
    }
};

 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

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    // 思路一：暴力 数据范围 10^4，那么走 10^4 次还没走到头就是有环了

    // 思路二：快慢指针
    // fast 和 slow指针 同时开始
    // 每次 fast指针移动两个结点，slow指针移动一个结点
    // 当 fast 追上 slow 有环，反之如果 fast直接指向nullptr末尾，无环
    // 进阶：你能用 O(1)（即，常量）内存解决此问题吗？
    bool hasCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow)
                return true;
        }
        return false;
    }
};

 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

/**
 * Definition for singly-linked list.
 **/
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    // 法一：哈希表+ 设定一个最多循环次数

    // 法二：利用快慢指针相对的 速度，通过数学推导来找环 入口
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow) {
                while(slow != head){
                    slow = slow->next;
                    head = head->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

 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

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:
    // 重排链表思路如下：
    void reorderList(ListNode* head) {
        ListNode *fast = head, *slow = head;
        // 1. 快慢指针 找到中间结点 slow
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        // 2. 反转后半段 链表
        ListNode *pre = nullptr;
        ListNode *cur = slow, *nxt = nullptr;
        while(cur){
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        // 3. 循环迭代 每次修改head->next 指针 和 head2->next 指针
        ListNode *head2 = pre, *p = nullptr, *q = nullptr;
        while(head2->next){
            p = head->next; // 暂存 head下一个结点
            head->next = head2; // 第一次重排
            q = head2->next; // 暂存 head2下一个结点
            head2->next = p; // 第二次重排
            head = p, head2 = q; // head 和 head2 指向原来的next结点
        }
    }
};