LeetCode 热题 100

1. 哈希

1.1 两数之和

1. 1. 两数之和

   给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。
   示例 1：

   输入：nums = [2,7,11,15], target = 9
   输出：[0,1]
   解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

   示例 2：

   输入：nums = [3,2,4], target = 6
   输出：[1,2]

   示例 3：

   输入：nums = [3,3], target = 6
   输出：[0,1]

   提示

   思路：用一个哈希表来存储遍历过的元素，后续遍历如果需要的值在哈希表中有，那么就查找到了。

   Python

   class Solution:
   def twoSum(self, nums: List[int], target: int) -> List[int]:
       idx = {}
       for i, num in enumerate(nums):
           if target - num in idx:
               return [idx[target - num], i]
           idx[num] = i

   C++

   class Solution {
   public:
       vector<int> twoSum(vector<int>& nums, int target) {
           unordered_map<int, int> idx;
           for (int j = 0; ; j++) {
               auto it = idx.find(target - nums[j]);
               // 这里的 auto 是：unordered_map<int, int>::iterator
               if (it != idx.end()) {
                   return {it->second, j};
               }
               idx[nums[j]] = j;
           }
       }
   };

   C++的 map 和 unordered_map

   • map内部是红黑树，元素按键有序存储。查找、插入、删除都需要沿树查找路径，复杂度约为 log n。

   • unordered_map内部是哈希表，根据键的哈希值直接定位到桶(bucket)。平均情况 下查找是常数时间 O(1)。

   时间复杂度：$O(n)$。

   空间复杂度：$O(n)$。

1.2 字母异位词分组

2. 49. 字母异位词分组

   给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
   示例 1：

   输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
   输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
   解释：

   • 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
   • 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
   • 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

   示例 2：

   输入: strs = [""]
   输出: [[""]]

   示例 3：

   输入: strs = ["a"]
   输出: [["a"]]

   提示

   思路：一开始想过用Counter，可以区分出不同的字符串是否是一组字母异位词，但是仍然需要花费额外的时间去判断当前字符串是属于哪一组的字母异位词。因此改用sorted，排序后的字符串天然拥有唯一性，适合搭配哈希表来使用，key表示排序后的字符串，value使用一个列表来整合这组的字母异位词。

   Python

   class Solution:
   def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
       from collections import defaultdict
       dic = defaultdict(list)
       for s in strs: # O(n)
           sorted_s = ''.join(sorted(s)) # O(mlogm)
           dic[sorted_s].append(s)
       return list(dic.values())

   C++

   class Solution {
   public:
       vector<vector<string>> groupAnagrams(vector<string>& strs) {
           unordered_map<string, vector<string>> mp;
           for (string s : strs) {
               string sorted_s = s;
               ranges::sort(sorted_s);
               mp[sorted_s].push_back(s);
           }
           vector<vector<string>> res;
           for (auto [_, value] : mp) {
               res.push_back(value);
           }
           return res;
       }
   };

   时间复杂度：$O(nmlogm)$。其中 n 为 strs 的长度，m 为 strs[i] 的长度。每个字符串排序需要 $O(mlogm)$ 的时间，有 n 个字符串，所以总的时间复杂度为 $O(nmlogm)$。

   空间复杂度：$O(nm)$。

1.3 最长连续序列

3. 128. 最长连续序列

   给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
   示例 1：

   输入：nums = [100,4,200,1,3,2]
   输出：4
   解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

   示例 2：

   输入：nums = [0,3,7,2,5,8,4,6,0,1]
   输出：9

   示例 3：

   输入：nums = [1,0,1,2]
   输出：3

   提示

   思路：set拥有去除重复元素的功能，因此将nums放入哈希集合，此时注意如果2,3,4是连续的，那么1,2,3,4必然连续，因此如果遇到当前元素-1也在集合内部，避免重复计算直接跳过即可。

   Python

   class Solution:
   def longestConsecutive(self, nums: List[int]) -> int:
       st = set(nums)
       res = 0
       for x in st:
           if x - 1 in st:
               continue
           y = x + 1
           while y in st:
               y += 1
           res = max(res, y - x)
       return res

   C++

   class Solution {
   public:
       int longestConsecutive(vector<int>& nums) {
           unordered_set<int> st(nums.begin(), nums.end());
           int res = 0;
           for (int x : st) {
               if (st.contains(x - 1)) {
                   continue;
               }
               int y = x + 1;
               while (st.contains(y)) {
                   y++;
               }
               res = max(res, y - x);
           }
           return res;
       }
   };

   时间复杂度：$O(n)$。

   空间复杂度：$O(m)$。其中 m 是 nums 中的不同元素个数。

   C++中的 unordered_set 和 unordered_map

   • unordered_set<Key>，只存「键」，类似于哈希版集合{1, 2, 3}，用于判断某个元素是否存在。

   • unordered_map<Key, Value>，存「键 → 值」映射，哈希版字典{1: "one", 2: "two"}，通过 key 查找对应 value。

   • 相同点：底层都使用哈希表（hash table）实现，查找复杂度平均 O(1)，最坏 O(n)，元素无序存储，key 唯一（不允许重复）。

2. 双指针

2.1 移动零

1. 283. 移动零

   给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。
   示例 1：

   输入: nums = [0,1,0,3,12]
   输出: [1,3,12,0,0]

   示例 2：

   输入: nums = [0]
   输出: [0]

   提示

   思路：双指针的思路，慢指针初始指向 0 ，快指针遍历整个数组，遇到非 0 的数就用慢指针所在空间存储，同时慢指针+1，即指向下一个空位。

   Python

   class Solution:
   def moveZeroes(self, nums: List[int]) -> None:
       """
       Do not return anything, modify nums in-place instead.
       """
       i = 0
       for j, num in enumerate(nums):
           if num:
               nums[i], nums[j] = nums[j], nums[i]
               i += 1

   C++

   class Solution {
   public:
       void moveZeroes(vector<int>& nums) {
           int i = 0;
           for (int &x : nums) {
               if (x) {
                   swap(x, nums[i]);
                   i++;
               }
           }
       }
   };

2.2 盛最多水的容器

2. 11. 盛最多水的容器

   给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。
   示例 1：

   输入：[1,8,6,2,5,4,8,3,7]
   输出：49
   解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。（原图请跳转链接查看）

   示例 2：

   输入：height = [1,1]
   输出：1

   提示

   思路：关键是理解短板效应。如示例一的图，我们在首尾各使用一个指针，计算初始容积，移动指针，如果容积变大，则更新。问题是怎么移动，移动哪条边？假如我们移动长的边，例如左边红色的线，首先让它变短（右移一位），容积必然变小，因为矩形的长宽都短了，然后如果变长呢？长变短宽不变（因为短板效应，容积和短的边有关），因此我们只能移动短的边。

   重要

   思考：为什么相等时移动左右两边都可以？首先，如果遇到左右相等的情况，那么里面都是比当前宽短的和只有一根比宽长的这两种情况，是可以直接 break 的，因为不可能比当前容积大，更不用说比从初始就记录的 res 大了，因此自然移动左右都可以。而只有当内部有两根以上长的情况，才会可能比当前容积大，既然有两根以上，那么先移动左还是右自然最终都会移到这两根内部最长的上面。

   Python

   class Solution:
   def maxArea(self, height: List[int]) -> int:
       left = res = 0
       right = len(height) - 1
       while left < right:
           area = (right - left) * min(height[left], height[right])
           res = max(res, area)
           if height[left] < height[right]:
               left += 1
           else:
               right -= 1
       return res

   C++

   class Solution {
   public:
       int maxArea(vector<int>& height) {
           int left = 0, res = 0, right = height.size() - 1;
           while (left <right) {
               int area = (right - left) * min(height[left], height[right]);
               res = max(res, area);
               height[left] < height[right] ? left++ : right--;
           }
           return res;
       }
   };

   时间复杂度：$O(n)$。

   空间复杂度：$O(1)$。

2.3 三数之和

3. 15. 三数之和

   给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。
   示例 1：

   输入：nums = [-1,0,1,2,-1,-4]
   输出：[[-1,-1,2],[-1,0,1]]
   解释：
   nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
   nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
   nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
   不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
   注意，输出的顺序和三元组的顺序并不重要。

   示例 2：

   输入：nums = [0,1,1]
   输出：[]
   解释：唯一可能的三元组和不为 0 。

   示例 3：

   输入：nums = [0,0,0]
   输出：[[0,0,0]]
   解释：唯一可能的三元组和为 0 。

   提示

   思路：要充分利用已经排好序的信息，面多加水水多加面。用一个指针i遍历数组（优化：避免重复，遇到和上一个元素相同则跳过），j和k以首尾的方式来遍历i后面的部分，如果ijk大于0，那么k变小，如果ijk小于0，那么k变大，当ijk等于0时，就找到了，存储结果，jk同时中间移动一位，查找其他可能（优化：避免重复，遇到j和j-1、k和k+1相同则跳过）。

   Python

   class Solution:
   def threeSum(self, nums: List[int]) -> List[List[int]]:
       nums.sort() # O(nlogn)
       res = []
       n = len(nums)
       for i in range(n - 2): # O(n)
           if i > 0 and nums[i] == nums[i - 1]: # 优化：避免重复
               continue
           if nums[i] + nums[i + 1] + nums[i + 2] > 0: # 优化：最小的三数大于0，则后续不可能等于0
               break
           if nums[i] + nums[-2] + nums[-1] < 0: # 优化：当前和最大的两数小于0，则后续不可能等于0
               continue
           j = i + 1
           k = n - 1
           while j < k: # O(n)
               if nums[i] + nums[j] + nums[k] > 0:
                   k -= 1
               elif nums[i] + nums[j] + nums[k] < 0:
                   j += 1
               else:
                   res.append([nums[i], nums[j], nums[k]])
                   j += 1
                   while nums[j] == nums[j - 1] and j < k: # 优化：避免重复
                       j += 1
                   k -= 1
                   while nums[k] == nums[k + 1] and j < k: # 优化：避免重复
                       k -= 1
       return res

   C++

   class Solution {
   public:
       vector<vector<int>> threeSum(vector<int>& nums) {
           vector<vector<int>> res;
           ranges::sort(nums);
           int n = nums.size();
           for (int i = 0; i < n - 2; i++) {
               if (i > 0 && nums[i] == nums[i - 1]) continue;
               if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
               if (nums[i] + nums[n - 1] + nums[n - 2] < 0) continue;
               int j = i + 1, k = n - 1;
               while (j < k) {
                   if (nums[i] + nums[j] + nums[k] > 0) k--;
                   else if (nums[i] + nums[j] + nums[k] < 0) j++;
                   else {
                       res.push_back({nums[i], nums[j], nums[k]});
                       for (j++; j < k && nums[j] == nums[j - 1]; j++);
                       for (k--; j < k && nums[k] == nums[k + 1]; k--);
                   }
               }
           }
           return res;
       }
   };

   时间复杂度：$O(n^2)$。其中 n 为 nums 的长度。排序 $O(nlogn)$。外层循环枚举第一个数，就变成 167. 两数之和 II - 输入有序数组 了，做法是 $O(n)$ 双指针。所以总的时间复杂度为 $O(n^2)$。

   空间复杂度：$O(1)$。

2.4 接雨水

4. 42. 接雨水

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

   输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
   输出：6
   解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

   示例 2：

   输入：height = [4,2,0,3,2,5]
   输出：9

   提示

   思路：考虑某一个位置能接多少水，取决于这个位置左边最大值和右边最大值，换种说法，可以把这个位置看成有一个木桶，木桶的左长度就是左边最大值，右长度就是右边的最大值，当前接水量为左长度和右长度的最小值减去柱子高度（短板效应）。因此很自然想到分别计算出前缀最大值和后缀最大值。

   Python

   class Solution:
   def trap(self, height: List[int]) -> int:
       n = len(height)
       res = 0
       
       # 计算前缀最大值
       pre_max = [0] * n
       pre_max[0] = height[0]
       for i in range(1, n): # O(n)
           pre_max[i] = max(pre_max[i-1], height[i])
   
       # 计算后缀最大值
       suf_max = [0] * n
       suf_max[-1] = height[-1]
       for i in range(n - 2, -1, -1): # O(n)
           suf_max[i] = max(suf_max[i+1], height[i])
   
       # 计算每个位置的雨水
       for i in range(n): # O(n)
           res += min(pre_max[i], suf_max[i]) - height[i]
       return res

   C++

   class Solution {
   public:
       int trap(vector<int>& height) {
           int n = height.size();
           
           // 计算前缀最大值
           vector<int> pre_max(n);
           pre_max[0] = height[0];
           for (int i = 1; i < n; i++) {
               pre_max[i] = max(pre_max[i - 1], height[i]);
           }
   
           // 计算后缀最大值
           vector<int> suf_max(n);
           suf_max[n - 1] = height[n - 1];
           for (int j = n - 2; j >= 0; j--) {
               suf_max[j] = max(suf_max[j + 1], height[j]);
           }
   
           // 计算每个位置的雨水
           int res = 0;
           for (int i = 0; i < n; i++) {
               res += min(suf_max[i], pre_max[i]) - height[i];
           }
           return res;
       }
   };

   时间复杂度：$O(n)$。

   空间复杂度：$O(n)$。

   双指针的做法

   优化空间复杂度：考虑现在只知道前几项的最大值和后几项的最大值，中间的状态不知道，但如果后几项中的最大值比前几项大，根据短板效应，即使中间状态还有更大的板子，装水的量也取决于短板，因此前几项的水量可以直接计算，反之亦然。注意 while 循环可以不加等号，因为在「谁小移动谁」的规则下，相遇的位置一定是最高的柱子，这个柱子是无法接水的。

   Python

   class Solution:
   def trap(self, height: List[int]) -> int:
       pre_max = suf_max = res = 0
       left, right = 0, len(height) - 1
   
       while left < right: # O(n)
           pre_max = max(pre_max, height[left])
           suf_max = max(suf_max, height[right])
           if pre_max < suf_max:
               res += pre_max - height[left]
               left += 1
           else:
               res += suf_max - height[right]
               right -= 1
       return res

   C++

   class Solution {
   public:
       int trap(vector<int>& height) {
           int pre_max = 0, suf_max = 0, res = 0;
           int left = 0, right = height.size() - 1;
           while (left < right) {
               pre_max = max(pre_max, height[left]);
               suf_max = max(suf_max, height[right]);
               res += pre_max < suf_max ? pre_max - height[left++] : suf_max - height[right--];
           }
           return res;
       }
   };

   时间复杂度：$O(n)$。

   空间复杂度：$O(1)$。

3. 滑动窗口

3.1 无重复字符的最长子串

1. 3. 无重复字符的最长子串

   给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
   示例 1：

   输入: s = "abcabcbb"
   输出: 3
   解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

   示例 2：

   输入: s = "bbbbb"
   输出: 1
   解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

   示例 3：

   输入: s = "pwwkew"
   输出: 3
   解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
   请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

   提示

   思路：典型的不定长滑动窗口思想。入——出——更新。用一个计数器来记录窗口内每种元素的个数，如果遇到重复元素，则收缩窗口。

   Python

   class Solution:
   def lengthOfLongestSubstring(self, s: str) -> int:
   
       from collections import Counter
       cnt = Counter()
       left = 0
       res = 0
       for right, c in enumerate(s):
           cnt[c] += 1
           while cnt[c] > 1:
               cnt[s[left]] -= 1
               left += 1
           res = max(res, right - left + 1)
       return res

   C++

   class Solution {
   public:
       int lengthOfLongestSubstring(string s) {
           unordered_map<char, int> cnt;
           int left = 0, res = 0;
           for (int right = 0; right < s.length(); right++) {
               char c = s[right];
               cnt[c]++;
               while (cnt[c] > 1) {
                   cnt[s[left]]--;
                   left++;
               }
               res = max(res, right - left + 1);
           }
           return res;
       }
   };

   时间复杂度：$O(n)$。

   空间复杂度：$O(n)$。

3.2 找到字符串中所有字母异位词

2. 438. 找到字符串中所有字母异位词

   给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
   示例 1：

   输入: s = "cbaebabacd", p = "abc"
   输出: [0,6]
   解释:
   起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
   起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

   示例 2：

   输入: s = "abab", p = "ab"
   输出: [0,1,2]
   解释:
   起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
   起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
   起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

   提示

   思路：滑动窗口思想。

   重要

   定长滑动窗口思想。维护长度为 len(p) 的定长滑动窗口，如果当前窗口匹配上指定窗口，则加入左端点下标。无论是否匹配，都要丢弃左端元素进入下一轮匹配。为了使用 == 判断两个计数器是否等价，要记得删除数量为 0 的 key。

   Python

   class Solution:
   def findAnagrams(self, s: str, p: str) -> List[int]:
       cnt_p = Counter(p)
       cnt_s = Counter()
       res = []
       for right, c in enumerate(s):
           cnt_s[c] += 1
           left = right - len(p) + 1
           if left < 0:
               continue
           if cnt_s == cnt_p:
               res.append(left)
           cnt_s[s[left]] -= 1
           if cnt_s[s[left]] == 0:
               del cnt_s[s[left]]
       return res

   C++

   class Solution { // 辅助空间用数组做法
   public:
       vector<int> findAnagrams(string s, string p) {
           array<int, 26> cnt_s{};
           array<int, 26> cnt_p{};
           vector<int> res;
           for (char c : p) {
               cnt_p[c - 'a']++;
           }
           for (int right = 0; right < s.length(); right++) {
               cnt_s[s[right] - 'a'] += 1;
               int left = right - p.length() + 1;
               if (left < 0) continue;
               if (cnt_p == cnt_s) {
                   res.push_back(left);
               }
               cnt_s[s[left] - 'a'] -= 1;
           }
           return res;
       }
   };

   C++

   class Solution { // 辅助空间用哈希表做法
   public:
       vector<int> findAnagrams(string s, string p) {
           unordered_map<char, int> cnt_s;
           unordered_map<char, int> cnt_p;
           vector<int> res;
           for (char c : p) {
               cnt_p[c]++;
           }
           for (int right = 0; right < s.length(); right++) {
               cnt_s[s[right]] += 1;
               int left = right - p.length() + 1;
               if (left < 0) continue;
               if (cnt_p == cnt_s) {
                   res.push_back(left);
               }
               if (--cnt_s[s[left]] == 0) {
                   cnt_s.erase(s[left]);
               }
           }
           return res;
       }
   };

   时间复杂度：$O(∣Σ∣m+n)$，其中 m 是 s 的长度，n 是 p 的长度，∣Σ∣=26 是字符集合的大小。

   空间复杂度：$O(∣Σ∣)$。返回值不计入。

   重要

   不定长滑动窗口思想。只使用一个计数器cnt统计p的字符，每遍历一个s中的元素就减少cnt的数量，如果减少当前元素数量后计数器没有负数且长度也相等，那么就匹配成功。

   Python

   class Solution:
   def findAnagrams(self, s: str, p: str) -> List[int]:
       cnt = Counter(p)
       left = 0
       res = []
       for right, c in enumerate(s):
           cnt[c] -= 1
           while cnt[c] < 0:
               cnt[s[left]] += 1
               left += 1
           if right - left + 1 == len(p):
               res.append(left)
       return res

   C++

   class Solution {
   public:
       vector<int> findAnagrams(string s, string p) {
           int cnt[26] = {0};
           vector<int> res;
           int left = 0;
           for (char c : p) {
               cnt[c - 'a']++;
           }
           for (int right = 0; right < s.length(); right++) {
               cnt[s[right] - 'a']--;
               while (cnt[s[right] - 'a'] < 0) {
                   cnt[s[left] - 'a']++;
                   left++;
               }
               if (right - left + 1 == p.length()) res.push_back(left);
           }
           return res;
       }
   };

   时间复杂度：$O(m+n)$，其中 m 是 s 的长度，n 是 p 的长度。虽然写了个二重循环，但是内层循环中对 left 加一的总执行次数不会超过 m 次，所以滑窗的时间复杂度为 $O(m)$。

   空间复杂度：$O(∣Σ∣)$，其中 ∣Σ∣=26 是字符集合的大小。返回值不计入。

4. 子串

4.1 和为 K 的子数组

1. 560. 和为 K 的子数组

   给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。
   示例 1：

   输入：nums = [1,1,1], k = 2
   输出：2

   示例 2：

   输入：nums = [1,2,3], k = 3
   输出：2

   提示

   思路：先转化为前缀和的思路，再转化为两数之和，灵神的思路太妙了，建议多看几遍灵神的题解。先得到前缀和，再拿前缀和做两数之和。

   Python

   class Solution:
   def subarraySum(self, nums: List[int], k: int) -> int:
       s = [0] * (len(nums) + 1)
       for i, x in enumerate(nums):
           s[i + 1] = s[i] + x
       res = 0
       cnt = defaultdict(int)
       for sj in s:
           res += cnt[sj - k]
           cnt[sj] += 1
       return res

   C++

   class Solution {
   public:
       int subarraySum(vector<int>& nums, int k) {
           vector<int> pre_sum;
           int res = 0;
           pre_sum.resize(nums.size() + 1);
           for (int i = 0; i < nums.size(); i++) {
               pre_sum[i + 1] = pre_sum[i] + nums[i];
           }
           unordered_map<int, int> cnt;
           for (int x : pre_sum) {
               res += cnt.contains(x - k) ? cnt[x - k] : 0;
               cnt[x]++;
           }
           return res;
       }
   };

   时间复杂度：$O(n)$，其中 n 为 nums 的长度。

   空间复杂度：$O(n)$。

4.2 滑动窗口最大值

2. 239. 滑动窗口最大值

   给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
   示例 1：

   输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
   输出：[3,3,5,5,6,7]
   解释：
   滑动窗口的位置 最大值

   ---

   [1 3 -1] -3 5 3 6 7 3
   1 [3 -1 -3] 5 3 6 7 3
   1 3 [-1 -3 5] 3 6 7 5
   1 3 -1 [-3 5 3] 6 7 5
   1 3 -1 -3 [5 3 6] 7 6
   1 3 -1 -3 5 [3 6 7] 7

   示例 2：

   输入：nums = [1], k = 1
   出：[1]

   提示

   思路：单调栈。用一个双端队列构造一个从大到小的单调栈，无非是入和出的逻辑，如果当前元素比队尾元素大，那么不符合单调栈，队尾元素出列（右端），直到符合才入栈；如果队头元素超过了k大小的窗口，需要及时出列（左端）；每一轮循环栈内最大元素（左端）就是当前窗口的最大值。

   Python

   class Solution:
   def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
       from collections import deque
       q = deque()
       res = []
       for i, num in enumerate(nums):
           while q and num > nums[q[-1]]:
               q.pop()
           q.append(i)
           left = i - k + 1
           if left > q[0]:
               q.popleft()
           if left >= 0:
               res.append(nums[q[0]])
       return res

   C++

   class Solution {
   public:
       vector<int> maxSlidingWindow(vector<int>& nums, int k) {
           int n = nums.size();
           deque<int> q;
           vector<int> res(n - k + 1);
           for (int i = 0; i < n; i++) {
               while (!q.empty() && nums[i] > nums[q.back()]) {
                   q.pop_back();
               }
               q.push_back(i);
               int left = i - k + 1;
               if (left > q.front()) {
                   q.pop_front();
               }
               if (left >= 0) {
                   res[left] = nums[q.front()];
               }
           }
           return res;
       }
   };

   时间复杂度：$O(n)$，其中 n 为 nums 的长度。由于每个下标至多入队出队各一次，所以二重循环的循环次数是 O(n) 的。

   空间复杂度：$O(min(k,U))$，其中 U 是 nums 中的不同元素个数（本题至多为 20001）。双端队列至多有 k 个元素，同时又没有重复元素，所以也至多有 U 个元素，所以空间复杂度为 $O(min(k,U))$。返回值的空间不计入。

4.3 最小覆盖子串

1. 76. 最小覆盖子串

   给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 '' 。注意：对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串，我们保证它是唯一的答案
   示例 1：

   输入：s = "ADOBECODEBANC", t = "ABC"
   输出："BANC"
   解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

   示例 2：

   输入：s = "a", t = "a"
   输出："a"
   解释：整个字符串 s 是最小覆盖子串。

   示例 3：

   输入: s = "a", t = "aa"
   输出: ""
   解释: t 中两个字符 'a' 均应包含在 s 的子串中，
   因此没有符合条件的子字符串，返回空字符串。

   提示

   思路：非定长滑动窗口思路。初始化一个答案左指针和一个答案右指针，分别指向字符串头前和字符串尾后。每轮循环s的计数器录入s的一个字符，如果s的计数器涵盖（看示例 1，s 的子串 BANC 中每个字母的出现次数，都大于等于 t=ABC 中每个字母的出现次数，这就叫涵盖。）t的计数器，那么表明覆盖了，如果当前左右指针长度比答案指针短，就更新。

   Python

   class Solution:
   def minWindow(self, s: str, t: str) -> str:
       cnt_s = Counter()
       cnt_t = Counter(t)
       res_left = -1, res_right = len(s)
       left = 0
       for right, c in enumerate(s):
           cnt_s[c] += 1
           while cnt_s >= cnt_t:
               if right - left < res_right - res_left:
                   res_left, res_right = left, right
               cnt_s[s[left]] -= 1
               left += 1
       return "" if res_left < 0 else s[res_left : res_right + 1]

   C++

   时间复杂度：$O(∣Σ∣m+n)$，其中 m 为 s 的长度，n 为 t 的长度，∣Σ∣ 为字符集合的大小，本题字符均为英文字母，所以 ∣Σ∣=52。注意 left 只会增加不会减少，left 每增加一次，我们就花费 $O(∣Σ∣)$ 的时间。因为 left 至多增加 m 次，所以二重循环的时间复杂度为 $O(∣Σ∣m)$，再算上统计 t 字母出现次数的时间 $O(n)$，总的时间复杂度为 $O(∣Σ∣m+n)$。

   空间复杂度：$O(∣Σ∣)$。如果创建了大小为 128 的数组，则 ∣Σ∣=128。

5. 普通数组

5.1 最大子数组和

1. 53. 最大子数组和

   给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
   示例 1：

   输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
   输出：6
   解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

   示例 2：

   输入：nums = [1]
   输出：1

   示例 3：

   输入：nums = [5,4,-1,7,8]
   输出：23

   提示

   思路：前缀和+贪心。看到连续子数组，就要想到可以转化为两个前缀和之差，需要子数组和最大，那么就是前缀和差值最大，也就是被减数最大，减数最小，类似买股票，低买高卖。只需要维护前缀最小值和最大值（直接计算最大答案）。

   Python

   class Solution:
   def maxSubArray(self, nums: List[int]) -> int:
       min_pre_sum = pre_sum = 0
       res = -inf
       for num in nums:
           pre_sum += num
           res = max(res, pre_sum - min_pre_sum)
           min_pre_sum = min(min_pre_sum, pre_sum)
       return res

   C++

   class Solution {
   public:
       int maxSubArray(vector<int>& nums) {
           int pre_sum = 0, min_pre_sum = 0;
           int res = INT_MIN;
           for (int x : nums) {
               pre_sum += x;
               res = max(res, pre_sum - min_pre_sum);
               min_pre_sum = min(min_pre_sum, pre_sum);
           }
           return res;
       }
   };

   时间复杂度：$O(n)$，其中 n 为 nums 的长度。

   空间复杂度：$O(1)$。仅用到若干额外变量。

5.2 合并区间

1. 56. 合并区间

   以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
   示例 1：

   输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
   输出：[[1,6],[8,10],[15,18]]
   解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

   示例 2：

   输入：intervals = [[1,4],[4,5]]
   输出：[[1,5]]
   解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

   示例 3：

   输入：intervals = [[4,7],[1,4]]
   输出：[[1,7]]
   解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

   提示

   思路：排序。按照左端点排序，如果左边区间的右端点大于右边区间的左端点，那么就可以合并，右端点选最大的，否则寻找下一个合并区间。

   Python

   class Solution:
   def merge(self, intervals: List[List[int]]) -> List[List[int]]:
       intervals.sort(key=lambda x: x[0])
       res = []
       for p in intervals:
           if res and res[-1][1] >= p[0]:
               res[-1][1] = max(p[1], res[-1][1])
           else:
               res.append(p)
       return res

   C++

   class Solution {
   public:
       vector<vector<int>> merge(vector<vector<int>>& intervals) {
           vector<vector<int>> res;
           ranges::sort(intervals);
           for (auto p : intervals) {
               if (!res.empty() && res.back()[1] >= p[0]) {
                   res.back()[1] = max(res.back()[1], p[1]);
               }
               else {
                   res.emplace_back(p);
               }
           }
           return res;
       }
   };

   重要

   emplace_back() 是 push_back() 的一种更高效写法。

   它会在容器末尾原地构造一个新元素，而不是先创建一个临时变量再拷贝进去。

   时间复杂度：$O(nlogn)$，其中 n 是 intervals 的长度。瓶颈在排序上。

   空间复杂度：$O(1)$。排序的栈开销和返回值不计入。

5.3 轮转数组

1. 189. 轮转数组

   给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
   示例 1：

   输入: nums = [1,2,3,4,5,6,7], k = 3
   输出: [5,6,7,1,2,3,4]
   解释:
   向右轮转 1 步: [7,1,2,3,4,5,6]
   向右轮转 2 步: [6,7,1,2,3,4,5]
   向右轮转 3 步: [5,6,7,1,2,3,4]

   示例 2：

   输入：nums = [-1,-100,3,99], k = 2
   输出：[3,99,-1,-100]
   解释:
   向右轮转 1 步: [99,-1,-100,3]
   向右轮转 2 步: [3,99,-1,-100]

   提示

   思路：前缀积和后缀积。

   Python

   class Solution:
   def rotate(self, nums: List[int], k: int) -> None:
       """
       Do not return anything, modify nums in-place instead.
       """
       def reverse(i, j):
           while i < j:
               nums[i], nums[j] = nums[j], nums[i]
               i += 1
               j -= 1
       n = len(nums)
       k = k % n
       reverse(0, n - 1)
       reverse(0, k - 1)
       reverse(k, n - 1)

   C++

   class Solution {
   public:
       void rotate(vector<int>& nums, int k) {
           k %= nums.size();
           ranges::reverse(nums.begin(), nums.end());
           reverse(nums.begin(), nums.begin() + k);
           reverse(nums.begin() + k, nums.end());
       }
   };

   时间复杂度：$O(n)$，其中 n 是 nums 的长度。

   空间复杂度：$O(1)$。

5.4 除自身以外数组的乘积

1. 238. 除自身以外数组的乘积

   给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。
   示例 1：

   输入: nums = [1,2,3,4]
   输出: [24,12,8,6]

   示例 2：

   输入: nums = [-1,1,0,-3,3]
   输出: [0,0,9,0,0]

   提示

   思路：前缀积和后缀积。分别算出前缀积和后缀积，那么前缀积乘后缀积就是除自身以外数组的乘积。

   Python

   class Solution:
   def productExceptSelf(self, nums: List[int]) -> List[int]:
       n = len(nums)
       pre = [1] * n
       for i in range(1, n):
           pre[i] = pre[i - 1] * nums[i - 1]
       suf = [1] * n
       for i in range(n - 2, -1, -1):
           suf[i] = suf[i + 1] * nums[i + 1]
       return [p * s for p, s in zip(pre, suf)]

   C++

   class Solution {
   public:
       vector<int> productExceptSelf(vector<int>& nums) {
           int n = nums.size();
           vector<int> pre(n, 1);
           vector<int> suf(n, 1);
           vector<int> res(n);
           for (int i = 1; i < n; i++) {
               pre[i] = pre[i - 1] * nums[i - 1];
           }
           for (int i = n - 2; i >= 0; i--) {
               suf[i] = suf[i + 1] * nums[i + 1];
           }
           for (int i = 0; i < n; i++) {
               res[i] = pre[i] * suf[i];
           }
           return res;
       }
   };

   时间复杂度：$O(n)$，其中 n 是 nums 的长度。

   空间复杂度：$O(n)$。

5.5 缺失的第一个正数

1. 41. 缺失的第一个正数

   给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
   示例 1：

   输入：nums = [1,2,0]
   输出：3
   解释：范围 [1,2] 中的数字都在数组中。

   示例 2：

   输入：nums = [3,4,-1,1]
   输出：2
   解释：1 在数组中，但 2 没有。

   示例 3：

   输入：nums = [7,8,9,11,12]
   输出：1
   解释：最小的正数 1 没有出现。

   提示

   思路：灵神的排座位思路太神了。

   Python

   class Solution:
   def firstMissingPositive(self, nums: List[int]) -> int:
       n = len(nums)
       for i in range(n):
           while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
               j = nums[i] - 1
               nums[i], nums[j] = nums[j], nums[i]
           
       for i in range(n):
           if nums[i] != i + 1:
               return i + 1
       return n + 1

   C++

   class Solution {
   public:
       int firstMissingPositive(vector<int>& nums) {
           int n = nums.size();
           for (int i = 0; i < n; i++) {
               while (nums[i] >= 1 && 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;
       }
   };

   时间复杂度：$O(n)$，其中 n 是 nums 的长度。虽然我们写了个二重循环，但每次交换都会把一个学生换到正确的座位上，所以总交换次数至多为 n，所以内层循环的总循环次数是 $O(n)$ 的，所以时间复杂度是 $O(n)$。

   空间复杂度：$O(1)$。

6. 矩阵

6.1 矩阵置零

1. 73. 矩阵置零

   给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
   示例 1：

   输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
   输出：[[1,0,1],[0,0,0],[1,0,1]]

   示例 2：

   输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
   输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

   提示

   思路：分别保存有0的行和列，然后遍历矩阵将有0的行和列赋值0。

   Python

   class Solution:
   def setZeroes(self, matrix: List[List[int]]) -> None:
       """
       Do not return anything, modify matrix in-place instead.
       """
       row_has_0 = [0 in row for row in matrix]
       col_has_0 = [0 in col for col in zip(*matrix)]
       for i, row in enumerate(row_has_0):
           for j, col in enumerate(col_has_0):
               if row or col:
                   matrix[i][j] = 0

   C++

   class Solution {
   public:
       void setZeroes(vector<vector<int>>& matrix) {
           int m = matrix.size(), n = matrix[0].size();
           vector<int8_t> row_has_0(m);
           vector<int8_t> col_has_0(n);
           for (int i = 0; i < m; i++) {
               for (int j = 0; j < n; j++) {
                   if (matrix[i][j] == 0) {
                       row_has_0[i] = col_has_0[j] = 1;
                   }
               }
           }
           for (int i = 0; i < m; i++) {
               for (int j = 0; j < n; j++) {
                   if (row_has_0[i] || col_has_0[j]) {
                       matrix[i][j] = 0;
                   }
               }
           }
       }
   };

   时间复杂度：$O(mn)$，其中 m 和 n 分别是 matrix 的行数和列数。

   空间复杂度：$O(m+n)$。

6.2 螺旋矩阵

1. 54. 螺旋矩阵

   给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素
   示例 1：

   输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
   输出：[[1,0,1],[0,0,0],[1,0,1]]

   示例 2：

   输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
   输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

   提示

   思路：用一个数组保存四个方向，判断下一个位置，行或列越界或已经访问过，那么改到下一个方向。

   Python

   DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)  # 右下左上
   
   class Solution:
       def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
           m, n = len(matrix), len(matrix[0])
           ans = []
           i = j = di = 0
           for _ in range(m * n):  # 一共走 mn 步
               ans.append(matrix[i][j])
               matrix[i][j] = None  # 标记，表示已经访问过（已经加入答案）
               x, y = i + DIRS[di][0], j + DIRS[di][1]  # 下一步的位置
               # 如果 (x, y) 出界或者已经访问过
               if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] is None:
                   di = (di + 1) % 4  # 右转 90°
               i += DIRS[di][0]
               j += DIRS[di][1]  # 走一步
           return ans

   C++

   class Solution {
   public:
       vector<int> spiralOrder(vector<vector<int>>& matrix) {
           int m = matrix.size(), n = matrix[0].size();
           vector<int> res(m * n);
           int DIRS[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
           int i = 0, j = 0, dir = 0;
           for (int k = 0; k < m * n; k++) {
               res[k] = (matrix[i][j]);
               matrix[i][j] = INT_MAX;
               int x = i + DIRS[dir][0];
               int y = j + DIRS[dir][1];
               if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] == INT_MAX) {
                   dir = (dir + 1) % 4;
               }
               i += DIRS[dir][0];
               j += DIRS[dir][1];
           }
           return res;
           
       }
   };

   时间复杂度：$O(mn)$，其中 m 和 n 分别为 matrix 的行数和列数。

   空间复杂度：$O(1)$。返回值不计入。

6.3 旋转图像

1. 48. 旋转图像

   给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
   示例 1：

   输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
   输出：[[7,4,1],[8,5,2],[9,6,3]]

   示例 2：

   输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
   输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

   提示

   思路：顺时针旋转90°，等价先转置，再翻转每行。

   Python

   class Solution:
   def rotate(self, matrix: List[List[int]]) -> None:
       n = len(matrix)
       # 第一步：转置
       for i in range(n):
           for j in range(i):  # 遍历对角线下方元素
               matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
   
       # 第二步：行翻转
       for row in matrix:
           row.reverse()

   C++

   class Solution {
   public:
       void rotate(vector<vector<int>>& matrix) {
           int n = matrix.size();
           for (int i = 0; i < n; i++) {
               for (int j = 0; j < i; j++) {
                   swap(matrix[i][j], matrix[j][i]);
               }
           }
           for (auto &row : matrix) {
               ranges::reverse(row);
           }
       }
   };

   重要

   将两次循环优化成一次循环：上面的方法是遍历下三角，如果改成上三角就可以转置完直接翻转。

   Python

   class Solution:
   def rotate(self, matrix: List[List[int]]) -> None:
       n = len(matrix)
       for i, row in enumerate(matrix):
           for j in range(i + 1, n):  # 遍历对角线上方元素，做转置
               row[j], matrix[j][i] = matrix[j][i], row[j]
           row.reverse()  # 行翻转

   C++

   class Solution {
   public:
       void rotate(vector<vector<int>>& matrix) {
           int n = matrix.size();
           for (int i = 0; i < n; i++) {
               for (int j = i + 1; j < n; j++) {
                   swap(matrix[i][j], matrix[j][i]);
               }
               ranges::reverse(matrix[i]);
           }
       }
   };

   时间复杂度：$O(n^2)$，其中 n 是 matrix 的行数和列数。

   空间复杂度：$O(1)$。

6.4 搜索二维矩阵 II

1. 240. 搜索二维矩阵 II

   编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。
   示例 1：

   输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
   输出：true

   示例 2：

   输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
   输出：false

   提示

   思路：从右上角开始遍历，如果当前元素比 target 小，那么整行都比 target 小，行下移；如果当前元素比 target 大，列左移，不断逼近 target 。

   Python

   class Solution:
   def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
       m, n = len(matrix), len(matrix[0])
       i, j = 0, n - 1  # 从右上角开始
       while i < m and j >= 0:  # 还有剩余元素
           if matrix[i][j] == target:
               return True  # 找到 target
           if matrix[i][j] < target:
               i += 1  # 这一行剩余元素全部小于 target，排除
           else:
               j -= 1  # 这一列剩余元素全部大于 target，排除
       return False

   C++

   class Solution {
   public:
       bool searchMatrix(vector<vector<int>>& matrix, int target) {
           int m = matrix.size(), n = matrix[0].size();
           int i = 0, j = n - 1;
           while (i < m && j >= 0) {
               if (matrix[i][j] == target) {
                   return true;
               }
               else if (matrix[i][j] > target) {
                   j--;
               }
               else {
                   i++;
               }
           }
           return false;
       }
   };

   时间复杂度：$O(m+n)$，其中 m 和 n 分别为 matrix 的行数和列数。每次循环排除掉一行或者一列，一共 m+n 行列，最坏情况下需要排除 m+n−1 行列才能找到答案。

   空间复杂度：$O(1)$。

7. 链表

7.1 相交链表

1. 160. 相交链表

   给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。图示两个链表在节点 c1 开始相交：题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。自定义评测：评测系统 的输入如下（你设计的程序 不适用 此输入）：intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0； listA - 第一个链表；listB - 第二个链表；skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数；skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数；评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
   示例 1：

   输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
   输出：Intersected at '8'
   解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
   从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
   在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
   — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

   示例 2：

   输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
   输出：Intersected at '2'
   解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
   从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
   在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

   示例 3：

   输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
   输出：No intersection
   解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
   由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
   这两个链表不相交，因此返回 null 。

   提示

   思路：两个指针分别从AB的起点开始遍历，如果遇到null，则跳转至对方的起点，继续往后走，这样可以确保相交时走的路程一样。

   Python

   class Solution:
   def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
       p, q = headA, headB
       while p is not q:
           p = p.next if p else headB
           q = q.next if q else headA
       return p

   C++

   /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     ListNode *next;
   *     ListNode(int x) : val(x), next(NULL) {}
   * };
   */
   class Solution {
   public:
       ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
           ListNode *p = headA, *q = headB;
           while (p != q) {
               p = p ? p->next : headB;
               q = q ? q->next : headA;
           }
           return p;
       }
   };

   时间复杂度：$O(m+n)$，其中 m 是第一条链表的长度，n 是第二条链表的长度。除了交点，每个节点会被指针 p 访问至多一次，每个节点会被指针 q 访问至多一次。

   空间复杂度：$O(1)$。

7.2 反转链表

1. 206. 反转链表

   给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
   示例 1：

   输入：head = [1,2,3,4,5]
   输出：[5,4,3,2,1]

   示例 2：

   输入：head = [1,2]
   输出：[2,1]

   示例 3：

   输入：head = []
   输出：[]

   提示

   思路：经典三指针法，pre cur nxt。

   Python

   class Solution:
   def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
       pre = None
       cur = head
       while cur:
           nxt = cur.next
           cur.next = pre  # 把 cur 插在 pre 链表的前面（头插法）
           pre = cur
           cur = nxt
       return pre

   C++

   /**
   * 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* reverseList(ListNode* head) {
           ListNode *pre = nullptr;
           ListNode *cur = head;
           while (cur) {
               ListNode *nxt = cur->next;
               cur->next = pre;
               pre = cur;
               cur = nxt;
           }
           return pre;
       }
   };

   时间复杂度：$O(n)$，其中 n 为链表节点个数。

   空间复杂度：$O(1)$。

7.3 回文链表

1. 234. 回文链表

   给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
   示例 1：

   输入：head = [1,2,2,1]
   输出：true

   示例 2：

   输入：head = [1,2]
   输出：false

   提示

   思路：一题更比三题强，找到中间节点->翻转中间节点后的部分->两头一起往中间遍历判断是否是回文。

   Python

   class Solution:
   # 876. 链表的中间结点
   def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
       slow = fast = head
       while fast and fast.next:
           slow = slow.next
           fast = fast.next.next
       return slow
   
   # 206. 反转链表
   def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
       pre, cur = None, head
       while cur:
           nxt = cur.next
           cur.next = pre
           pre = cur
           cur = nxt
       return pre
   
   def isPalindrome(self, head: Optional[ListNode]) -> bool:
       mid = self.middleNode(head)
       head2 = self.reverseList(mid)
       while head2:
           if head.val != head2.val:  # 不是回文链表
               return False
           head = head.next
           head2 = head2.next
       return True

   C++

   /**
   * 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 {
       ListNode *middleNode(ListNode *head) {
           ListNode *fast = head, *slow = head;
           while (fast && fast->next) {
               fast = fast->next->next;
               slow = slow->next;
           }
           return slow;
       }
   
       ListNode *reverseList(ListNode *head) {
           ListNode *pre = nullptr;
           ListNode *cur = head;
           while (cur) {
               ListNode *nxt = cur->next;
               cur->next = pre;
               pre = cur;
               cur = nxt;
           }
           return pre;
       }
   
   public:
       bool isPalindrome(ListNode* head) {
           ListNode *middle = middleNode(head);
           ListNode *head2 = reverseList(middle);      
           while (head2) {
               if (head2->val != head->val) return false;
               head = head->next;
               head2 = head2->next;
           }
           return true;
       }
   };

   时间复杂度：$O(n)$，其中 n 是链表的长度（节点个数）。

   空间复杂度：$O(1)$。

7.4 环形链表

1. 141. 环形链表

   给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。
   示例 1：

   输入：head = [3,2,0,-4], pos = 1
   输出：true
   解释：链表中有一个环，其尾部连接到第二个节点。

   示例 2：

   输入：head = [1,2], pos = 0
   输出：true
   解释：链表中有一个环，其尾部连接到第一个节点。

   示例 3：

   输入：head = [1], pos = -1
   输出：false
   解释：链表中没有环。

   提示

   思路：类似找寻中间节点的思想，用两个快慢指针，如果慢指针能追上快指针，说明有环。

   Python

   class Solution:
   def hasCycle(self, head: Optional[ListNode]) -> bool:
       slow = fast = head  # 乌龟和兔子同时从起点出发
       while fast and fast.next:
           slow = slow.next  # 乌龟走一步
           fast = fast.next.next  # 兔子走两步
           if fast is slow:  # 兔子追上乌龟（套圈），说明有环
               return True
       return False  # 访问到了链表末尾，无环

   C++

   /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     ListNode *next;
   *     ListNode(int x) : val(x), next(NULL) {}
   * };
   */
   class Solution {
   public:
       bool hasCycle(ListNode *head) {
           ListNode *fast = head, *slow = head;
           while (fast && fast->next) {
               fast = fast->next->next;
               slow = slow->next;
               if (fast == slow) {
                   return true;
               }
           }
           return false;
       }
   };

   时间复杂度：$O(n)$，其中 n 是链表的长度。

   空间复杂度：$O(1)$。

7.5 环形链表 II

1. 142. 环形链表 II

   给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
   示例 1：

   输入：head = [3,2,0,-4], pos = 1
   输出：返回索引为 1 的链表节点
   解释：链表中有一个环，其尾部连接到第二个节点。

   示例 2：

   输入：head = [1,2], pos = 0
   输出：返回索引为 0 的链表节点
   解释：链表中有一个环，其尾部连接到第一个节点。

   示例 3：

   输入：head = [1], pos = -1
   输出：返回 null
   解释：链表中没有环。

   提示

   思路：用了一个很巧妙的数学证明，从快慢指针相遇点再走a步就是入环口，a是头走到入环口的距离。

   Python

   class Solution:
   def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
       slow = fast = head
       while fast and fast.next:
           slow = slow.next
           fast = fast.next.next
           if fast is slow:  # 相遇
               while slow is not head:  # 再走 a 步
                   slow = slow.next
                   head = head.next
               return slow
       return None

   C++

   /**
   * 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 *fast = head, *slow = head;
           while (fast && fast->next) {
               fast = fast->next->next;
               slow = slow->next;
               if (fast == slow) {
                   while (head != slow) {
                       head = head->next;
                       slow = slow->next;
                   }
                   return slow;
               }
           }
           return nullptr;
       }
   };

   时间复杂度：$O(n)$，其中 n 是链表的长度。

   空间复杂度：$O(1)$。

7.6 合并两个有序链表

1. 21. 合并两个有序链表

   将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
   示例 1：

   输入：l1 = [1,2,4], l2 = [1,3,4]
   输出：[1,1,2,3,4,4]

   示例 2：

   输入：l1 = [], l2 = []
   输出：[]

   示例 3：

   输入：l1 = [], l2 = [0]
   输出：[0]

   提示

   思路：使用一个哨兵作为起始结点，list1和list2谁小就加入谁，最后判断是否有剩余链表直接加入尾端。

   Python

   class Solution:
   def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
       cur = dummy = ListNode()  # 用哨兵节点简化代码逻辑
       while list1 and list2:
           if list1.val < list2.val:
               cur.next = list1  # 把 list1 加到新链表中
               list1 = list1.next
           else:  # 注：相等的情况加哪个节点都是可以的
               cur.next = list2  # 把 list2 加到新链表中
               list2 = list2.next
           cur = cur.next
       cur.next = list1 or list2  # 拼接剩余链表
       return dummy.next

   C++

   /**
       * 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 temp;
           ListNode *cur = &temp;
           while (list1 && list2) {
               if (list1->val < list2->val) {
                   cur->next = list1;
                   list1 = list1->next;
               }
               else {
                   cur->next = list2;
                   list2 = list2->next;
               }
               cur = cur->next;
           }
           cur->next = list1 ? list1 : list2;
           return temp.next;
       }
   };

   时间复杂度：$O(n + m)$，其中 n 是 list1 的长度，m 是 list2 的长度。

   空间复杂度：$O(1)$。

7.7 两数相加

1. 2. 两数相加

   给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
   示例 1：

   输入：l1 = [2,4,3], l2 = [5,6,4]
   输出：[7,0,8]
   解释：342 + 465 = 807.

   示例 2：

   输入：l1 = [0], l2 = [0]
   输出：[0]

   示例 3：

   输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
   输出：[8,9,9,9,0,0,0,1]

   提示

   思路：使用一个哨兵作为起始结点，list1和list2谁小就加入谁，最后判断是否有剩余链表直接加入尾端。

   Python

   class Solution:
   def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
       cur = dummy = ListNode()  # 哨兵节点
       carry = 0  # 进位
       while l1 or l2 or carry:  # 有一个不是空节点，或者还有进位，就继续迭代
           if l1:
               carry += l1.val  # 节点值和进位加在一起
               l1 = l1.next  # 下一个节点
           if l2:
               carry += l2.val  # 节点值和进位加在一起
               l2 = l2.next  # 下一个节点
           cur.next = ListNode(carry % 10)  # 每个节点保存一个数位
           carry //= 10  # 新的进位
           cur = cur.next  # 下一个节点
       return dummy.next  # 哨兵节点的下一个节点就是头节点

   C++

   /**
   * 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 temp;
           ListNode *cur = &temp;
           int carry = 0;
           while (l1 || l2 || carry) {
               if (l1) {
                   carry += l1->val;
                   l1 = l1->next;
               }
               if (l2) {
                   carry += l2->val;
                   l2 = l2->next;
               }
               cur->next = new ListNode(carry % 10);
               cur = cur->next;
               carry /= 10;
           }
           return temp.next;
       }
   };

   时间复杂度：$O(n)$，其中 n 为 $l_1$ 长度和 $l_2$ 长度的最大值。

   空间复杂度：$O(1)$。

7.8 删除链表的倒数第 N 个结点

1. 19. 删除链表的倒数第 N 个结点

   给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
   示例 1：

   输入：head = [1,2,3,4,5], n = 2
   输出：[1,2,3,5]

   示例 2：

   输入：head = [1], n = 1
   输出：[]

   示例 3：

   输入：head = [1,2], n = 1
   输出：[1]

   提示

   思路：使用一个哨兵作为起始结点，用两个指针组成一把尺子，当尺子右端移到尾端，说明尺子左端就是倒数第 n 个结点的位置。

   Python

   class Solution:
   def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
       # 由于可能会删除链表头部，用哨兵节点简化代码
       left = right = dummy = ListNode(next=head)
       for _ in range(n):
           right = right.next  # 右指针先向右走 n 步
       while right.next:
           left = left.next
           right = right.next  # 左右指针一起走
       left.next = left.next.next  # 左指针的下一个节点就是倒数第 n 个节点
       return dummy.next

   C++

   /**
   * 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 temp(0, head);
           ListNode *left = &temp, *right = &temp;
           while (n--) {
               right = right->next;
           }
           while (right->next) {
               left = left->next;
               right = right->next;
           }
           ListNode *nxt = left->next;
           left->next = left->next->next;
           delete nxt;
           return temp.next;
       }
   };

   时间复杂度：$O(m)$，其中 m 为链表的长度。

   空间复杂度：$O(1)$。

7.9 两两交换链表中的节点

1. 24. 两两交换链表中的节点

   给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
   示例 1：

   输入：head = [1,2,3,4]
   输出：[2,1,4,3]

   示例 2：

   输入：head = []
   输出：[]

   示例 3：

   输入：head = [1]
   输出：[1]

   提示

   思路：使用一个哨兵作为起始结点，两个结点为一组依次翻转即可。

   Python

   class Solution:
   def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
       node0 = dummy = ListNode(next=head)  # 用哨兵节点简化代码逻辑
       node1 = head
       while node1 and node1.next:  # 至少有两个节点
           node2 = node1.next
           node3 = node2.next
   
           node0.next = node2  # 0 -> 2
           node2.next = node1  # 2 -> 1
           node1.next = node3  # 1 -> 3
   
           node0 = node1  # 下一轮交换，0 是 1
           node1 = node3  # 下一轮交换，1 是 3
       return dummy.next  # 返回新链表的头节点

   C++

   /**
   * 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 temp(0, head);
           ListNode *pre = &temp;
           while (pre->next && pre->next->next) {
               ListNode *cur = pre->next, *nxt = pre->next->next;
               cur->next = nxt->next;
               nxt->next = cur;
               pre->next = nxt;
               pre = cur;
           }
           return temp.next;
       }
   };

   时间复杂度：$O(n)$，其中 n 为链表的长度。

   空间复杂度：$O(1)$。

7.10 K 个一组翻转链表

1. 25. K 个一组翻转链表

   给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
   示例 1：

   输入：head = [1,2,3,4,5], k = 2
   输出：[2,1,4,3,5]

   示例 2：

   输入：head = [1,2,3,4,5], k = 3
   输出：[3,2,1,4,5]

   提示

   思路：使用一个哨兵作为起始结点，先算出链表的长度，然后k个一组翻转。

   Python

   class Solution:
   def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
       # 统计节点个数
       n = 0
       cur = head
       while cur:
           n += 1
           cur = cur.next
   
       p0 = dummy = ListNode(next=head)
       pre = None
       cur = head
   
       # k 个一组处理
       while n >= k:
           n -= k
           for _ in range(k):  # 同 92 题
               nxt = cur.next
               cur.next = pre  # 每次循环只修改一个 next，方便大家理解
               pre = cur
               cur = nxt
   
           # 见视频
           nxt = p0.next
           nxt.next = cur
           p0.next = pre
           p0 = nxt
       return dummy.next

   C++

   /**
   * 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* reverseKGroup(ListNode* head, int k) {
           ListNode dummy(0, head);
           ListNode *p = &dummy;
           int n = 0;
           while (head) {
               n++;
               head = head->next;
           }
           while (n >= k) {
               ListNode *pre = nullptr;
               ListNode *cur = p->next;
               for (int i = 0; i < k; i++) {
                   ListNode *nxt = cur->next;
                   cur->next = pre;
                   pre = cur;
                   cur = nxt;
               }
               ListNode *nxt = p->next;
               p->next = pre;
               nxt->next = cur;
               p = nxt;
               n -= k;
           }
           return dummy.next;
       }
   };

   时间复杂度：$O(n)$，其中 n 为链表的长度。

   空间复杂度：$O(1)$。

7.11 随机链表的复制

1. 138. 随机链表的复制

   给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。返回复制链表的头节点。用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：val：一个表示 Node.val 的整数。random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。你的代码 只 接受原链表的头节点 head 作为传入参数。
   示例 1：

   输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
   输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

   示例 2：

   输入：head = [[1,1],[2,1]]
   输出：[[1,1],[2,1]]

   示例 3：

   输入：head = [[3,null],[3,0],[3,null]]
   输出：[[3,null],[3,0],[3,null]]

   提示

   思路：先在原链表的每个结点的后面复制出一份拷贝结点，随机指针指向空；然后遍历这个新的链表，拷贝结点的随机指针就应该指向原结点的随机指针的next结点；最后分离这两个链表。

   Python

   class Solution:
   def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
       if head is None:
           return None
   
       # 复制每个节点，把新节点直接插到原节点的后面
       cur = head
       while cur:
           cur.next = Node(cur.val, cur.next)
           cur = cur.next.next
   
       # 遍历交错链表中的原链表节点
       cur = head
       while cur:
           if cur.random:
               # 要复制的 random 是 cur.random 的下一个节点
               cur.next.random = cur.random.next
           cur = cur.next.next
   
       # 遍历交错链表中的新链表节点
       cur = head.next
       while cur.next:
           # 删除原链表的节点，即当前节点的下一个节点
           # 如果要恢复原链表，见另一份代码【Python3 写法二】
           cur.next = cur.next.next
           cur = cur.next
   
       # 返回 head.next 就相当于删除了原链表的头节点
       return head.next

   C++

   /*
   // 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) {
           if (head == nullptr) {
               return nullptr;
           }
           for (Node *cur = head; cur; cur = cur->next->next) {
               cur->next = new Node(cur->val, cur->next, nullptr);
           }
           for (Node *cur = head; cur; cur = cur->next->next) {
               if (cur->random) {
                   cur->next->random = cur->random->next;
               }
           }
           Node *new_head = head->next;
           Node *cur = head;
           for (; cur->next->next; cur = cur->next) {
               Node *copy = cur->next;
               cur->next = copy->next;
               copy->next = copy->next->next;
           }
           cur->next = nullptr;
           return new_head;
       }
   };

   时间复杂度：$O(n)$，其中 n 为链表的长度。

   空间复杂度：$O(1)$。

7.12 随机链表的复制

1. 148. 排序链表

   给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
   示例 1：

   输入：head = [4,2,1,3]
   输出：[1,2,3,4]

   示例 2：

   输入：head = [-1,5,3,4,0]
   输出：[-1,0,3,4,5]

   示例 3：

   输入：head = []
   输出：[]

   提示

   思路：归并排序的思路。先将链表归到一项（链表的中间节点），然后并（合并两个链表）。

   Python

   class Solution:
   # 876. 链表的中间结点（快慢指针）
   def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
       slow = fast = head
       while fast and fast.next:
           pre = slow  # 记录 slow 的前一个节点
           slow = slow.next
           fast = fast.next.next
       pre.next = None  # 断开 slow 的前一个节点和 slow 的连接
       return slow
   
   # 21. 合并两个有序链表（双指针）
   def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
       cur = dummy = ListNode()  # 用哨兵节点简化代码逻辑
       while list1 and list2:
           if list1.val < list2.val:
               cur.next = list1  # 把 list1 加到新链表中
               list1 = list1.next
           else:  # 注：相等的情况加哪个节点都是可以的
               cur.next = list2  # 把 list2 加到新链表中
               list2 = list2.next
           cur = cur.next
       cur.next = list1 if list1 else list2  # 拼接剩余链表
       return dummy.next
   
   def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
       # 如果链表为空或者只有一个节点，无需排序
       if head is None or head.next is None:
           return head
       # 找到中间节点 head2，并断开 head2 与其前一个节点的连接
       # 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3]
       head2 = self.middleNode(head)
       # 分治
       head = self.sortList(head)
       head2 = self.sortList(head2)
       # 合并
       return self.mergeTwoLists(head, head2)

   C++

   /**
   * 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 {
       ListNode *middleNode(ListNode* head) {
           ListNode *fast = head, *slow = head, *pre = head;
           while (fast && fast->next) {
               fast = fast->next->next;
               pre = slow;
               slow = slow->next;
           }
           pre->next = nullptr;
           return slow;
       }
       ListNode *mergeTwoLists(ListNode *l1, ListNode*l2) {
           ListNode dummy;
           ListNode *p = &dummy;
           while (l1 && l2) {
               if (l1->val < l2->val) {
                   p->next = l1;
                   l1 = l1->next;
               }
               else {
                   p->next = l2;
                   l2 = l2->next;
               }
               p = p->next;
           }
           p->next = l1 ? l1 : l2;
           return dummy.next;
       }
   public:
       ListNode* sortList(ListNode* head) {
           if (head == nullptr || head->next == nullptr) {
               return head;
           }
           ListNode *mid = middleNode(head);
           ListNode *l1 = sortList(head);
           ListNode *l2 =sortList(mid);
           ListNode *res = mergeTwoLists(l1, l2);
           return res;
       }
   };

   时间复杂度：$O(nlogn)$，其中 n 是链表长度。递归式 $T(n)=2T(n/2)+O(n)$，由主定理可得时间复杂度为 $O(nlogn)$。从图形上理解，递归深度是 $O(logn)$，每一层的链表长度之和是 $O(n)$。计算高为 $O(logn)$，底边长为 $O(n)$ 的矩形面积，得到 $O(nlogn)$。

   空间复杂度：$O(logn)$。递归需要 $O(logn)$ 的栈开销。

7.13 随机链表的复制

1. 148. 排序链表

   给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
   示例 1：

   输入：lists = [[1,4,5],[1,3,4],[2,6]]
   输出：[1,1,2,3,4,4,5,6]
   解释：链表数组如下：
   [
   1->4->5,
   1->3->4,
   2->6
   ]
   将它们合并到一个有序链表中得到。
   1->1->2->3->4->4->5->6

   示例 2：

   输入：lists = []
   输出：[]

   示例 3：

   输入：lists = [[]]
   输出：[]

   提示

   思路：也是归并的思路。先将链表均分成两份，然后并（合并两个链表）。

   Python

   class Solution:
   # 21. 合并两个有序链表
   def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
       cur = dummy = ListNode()  # 用哨兵节点简化代码逻辑
       while list1 and list2:
           if list1.val < list2.val:
               cur.next = list1  # 把 list1 加到新链表中
               list1 = list1.next
           else:  # 注：相等的情况加哪个节点都是可以的
               cur.next = list2  # 把 list2 加到新链表中
               list2 = list2.next
           cur = cur.next
       cur.next = list1 if list1 else list2  # 拼接剩余链表
       return dummy.next
   
   def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
       m = len(lists)
       if m == 0:
           return None
       if m == 1:
           return lists[0]  # 无需合并，直接返回
       left = self.mergeKLists(lists[:m // 2])  # 合并左半部分
       right = self.mergeKLists(lists[m // 2:])  # 合并右半部分
       return self.mergeTwoLists(left, right)  # 最后把左半和右半合并

   C++

   /**
   * 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 {
       ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
           ListNode dummy;
           ListNode *p = &dummy;
           while (l1 && l2) {
               if (l1->val < l2->val) {
                   p->next = l1;
                   l1 = l1->next;
               }
               else {
                   p->next = l2;
                   l2 = l2->next;
               }
               p = p->next;
           }
           p->next = l1 ? l1 : l2;
           return dummy.next;
       }
       ListNode *mergeKLists(vector<ListNode*>& lists, int i, int j) {
           int n = j - i;
           if (n == 0) {
               return nullptr;
           }
           if (n == 1) {
               return lists[i];
           }
           ListNode *l1 = mergeKLists(lists, i, i + n / 2);
           ListNode *l2 = mergeKLists(lists, i + n / 2, j);
           return mergeTwoLists(l1, l2);
       }
   public:
       ListNode* mergeKLists(vector<ListNode*>& lists) {
           return mergeKLists(lists, 0, lists.size());
       }
   };

   时间复杂度：$O(Llogm)$，其中 m 为 lists 的长度，L 为所有链表的长度之和。每个节点参与链表合并的次数为 $O(logm)$ 次，一共有 L 个节点，所以总的时间复杂度为 $O(Llogm)$。

   空间复杂度：$O(logm)$。递归深度为 $O(logm)$，需要 $O(logm)$ 的栈空间。Python 忽略切片产生的额外空间。