《LeetCode 热题 100》整整 100 题量大管饱题解套餐 上_leetcode热题top100 | 中等

1、哈希

Q1、两数之和

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]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

2、解题思路

1. 暴力枚举法：直接双重循环遍历所有可能的数对，检查它们的和是否等于目标值。这种方法的时间复杂度为 O(n²)，适用于小规模数据。
2. 哈希表优化：使用哈希表（字典）来存储已经遍历过的数字及其索引。对于当前数字 nums[i]，检查 target - nums[i] 是否存在于哈希表中。如果存在，则返回对应的索引；否则，将当前数字存入哈希表。这种方法的时间复杂度为 O(n)，适用于大规模数据。

3、代码实现

C++

class Solution {public: vector twoSum(vector& nums, int target) { unordered_map hash; // 使用哈希表存储数字及其索引 for (int i = 0; i < nums.size(); ++i) { int gap = target - nums[i]; // 计算目标值与当前数字的差值 if (hash.count(gap)) { // 检查差值是否存在于哈希表中 return {hash[gap], i}; // 如果存在，返回对应的索引 } hash[nums[i]] = i; // 否则，将当前数字及其索引存入哈希表 } return {-1, -1}; // 如果没有找到符合条件的数对，返回{-1, -1} }};

Java

class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> hash = new HashMap<>(); // 使用哈希表存储数字及其索引 for (int i = 0; i < nums.length; ++i) { int gap = target - nums[i]; // 计算目标值与当前数字的差值 if (hash.containsKey(gap)) { // 检查差值是否存在于哈希表中 return new int[] { hash.get(gap), i }; // 如果存在，返回对应的索引 } hash.put(nums[i], i); // 否则，将当前数字及其索引存入哈希表 } return new int[] { -1, -1 }; // 如果没有找到符合条件的数对，返回{-1, -1} }}

Python

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hash = {} # 使用字典存储数字及其索引 for i, num in enumerate(nums): gap = target - num # 计算目标值与当前数字的差值 if gap in hash: # 检查差值是否存在于字典中 return [hash[gap], i] # 如果存在，返回对应的索引 hash[num] = i # 否则，将当前数字及其索引存入字典 return [-1, -1] # 如果没有找到符合条件的数对，返回[-1, -1]

4、复杂度分析

• 时间复杂度为 O(n)
• 空间复杂度为 O(n)

Q2、字母异位词分组

1、题目描述

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

示例 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”]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

2、解题思路

1. 哈希表分组：使用哈希表来存储字母异位词的分组。哈希表的键是排序后的字符串，值是对应的原始字符串列表。
2. 排序键：对于每个字符串，先将其排序，排序后的字符串作为哈希表的键。这样，所有字母异位词排序后的结果相同，会被分到同一组。
3. 提取结果：遍历哈希表，将每个键对应的值（即字母异位词列表）添加到结果列表中。

3、代码实现

C++

class Solution {public: vector<vector> groupAnagrams(vector& strs) { unordered_map<string, vector> hash; // 哈希表存储排序后的字符串及其对应的原始字符串列表 // 遍历每个字符串, 排序后作为键存入哈希表 for (const auto& s : strs) { string tmp = s; sort(tmp.begin(), tmp.end()); // 排序字符串 hash[tmp].push_back( s); // 将排序后的字符串作为键，原始字符串添加到对应的列表中 } // 提取哈希表中的所有分组 vector<vector> ret; for (const auto& entry : hash) { ret.push_back(entry.second); // 将每个分组添加到结果列表中 } return ret; }};

Java

class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> hash = new HashMap<>(); // 哈希表存储排序后的字符串及其对应的原始字符串列表 // 遍历每个字符串，排序后作为键存入哈希表 for (String s : strs) { char[] chars = s.toCharArray(); Arrays.sort(chars); // 排序字符串 String sorted = new String(chars); if (!hash.containsKey(sorted)) { hash.put(sorted, new ArrayList<>()); // 如果键不存在，初始化一个新的列表 } hash.get(sorted).add(s); // 将原始字符串添加到对应的列表中 } // 提取哈希表中的所有分组 return new ArrayList<>(hash.values()); }}

Python

class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: hash = defaultdict(list) # 使用字典存储排序后的字符串及其对应的原始字符串列表 # 遍历每个字符串，排序后作为键存入字典 for s in strs: sorted_s = \'\'.join(sorted(s)) # 排序字符串 hash[sorted_s].append(s) # 将排序后的字符串作为键，原始字符串添加到对应的列表中 # 提取字典中的所有分组 return list(hash.values())

4、复杂度分析

• 时间复杂度为 O(n * k log k)
• 空间复杂度为 O(n)

Q3、最长连续序列

1、题目描述

给定一个未排序的整数数组 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

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

2、解题思路

1. 哈希表存储：使用哈希表（或集合）存储数组中的所有数字，以便快速查找某个数字是否存在。
2. 寻找序列起点：对于哈希表中的每个数字，检查是否存在比它小 1 的数字。如果不存在，说明当前数字可能是某个连续序列的起点。
3. 扩展序列：从序列起点开始，依次检查是否存在比当前数字大 1 的数字，并记录序列的长度。
4. 更新最长序列：在遍历过程中，不断更新记录的最长序列长度。

这种方法确保了每个数字最多被访问两次（一次作为起点，一次作为序列中的数字），因此时间复杂度为 O(n)。

3、代码实现

C++

class Solution {public: int longestConsecutive(vector& nums) { unordered_set hash(nums.begin(), nums.end()); // 使用哈希集合存储所有数字 int longestStack = 0; // 初始化最长序列长度为 0 for (const int& num : hash) { // 检查当前数字是否是某个连续序列的起点 if (!hash.count(num - 1)) { int currentNum = num; int currentStreak = 1; // 当前序列长度初始化为 1 // 扩展序列, 直到找不到下一个连续数字 while (hash.count(currentNum + 1)) {  currentNum += 1;  currentStreak += 1; } // 更新最长序列长度 longestStack = max(longestStack, currentStreak); } } return longestStack; }};

Java

class Solution { public int longestConsecutive(int[] nums) { Set<Integer> hash = new HashSet<>(); for (int num : nums) { hash.add(num); // 使用哈希集合存储所有数字 } int longestStreak = 0; // 初始化最长序列长度为0 for (int num : hash) { // 检查当前数字是否是某个连续序列的起点 if (!hash.contains(num - 1)) { int currentNum = num; int currentStreak = 1; // 当前序列长度初始化为1 // 扩展序列，直到找不到下一个连续数字 while (hash.contains(currentNum + 1)) {  currentNum += 1;  currentStreak += 1; } // 更新最长序列长度 longestStreak = Math.max(longestStreak, currentStreak); } } return longestStreak; }}

Python

class Solution: def longestConsecutive(self, nums: List[int]) -> int: hash_set = set(nums) # 使用集合存储所有数字 longest_streak = 0 # 初始化最长序列长度为0 for num in hash_set: # 检查当前数字是否是某个连续序列的起点 if num - 1 not in hash_set: current_num = num current_streak = 1 # 当前序列长度初始化为1 # 扩展序列，直到找不到下一个连续数字 while current_num + 1 in hash_set:  current_num += 1  current_streak += 1 # 更新最长序列长度 longest_streak = max(longest_streak, current_streak) return longest_streak

4、复杂度分析

• 时间复杂度为 O(n)
• 空间复杂度为 O(n)

2、双指针

Q4、移动零

1、题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

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

示例 2:

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

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

**进阶：**你能尽量减少完成的操作次数吗？

2、解题思路

1. 双指针法：

   • 左指针（left）：指向当前非零元素应该存放的位置。
   • 右指针（right）：遍历整个数组，寻找非零元素。
   • 当右指针遇到非零元素时，将其与左指针指向的位置交换，并将左指针右移。
   • 这样，所有的非零元素会被依次移动到数组的前面，而零元素会被“挤”到数组的末尾。

2. 优化操作：

   • 在交换时，可以避免不必要的交换操作。例如，如果 left 和 right 指向同一个位置，可以直接跳过交换。

   • 这样可以减少交换次数，提高效率。

3、代码实现

C++

class Solution {public: void moveZeroes(vector& nums) { int n = nums.size(), left = 0, right = 0; while (right < n) { if (nums[right] != 0) { if (left != right) // 避免不必要的交换 {  swap(nums[left], nums[right]); } left++; // 左指针右移 } right++; // 右指针右移 } }};

Java

class Solution { public void moveZeroes(int[] nums) { int n = nums.length, left = 0, right = 0; while (right < n) { if (nums[right] != 0) { if (left != right) { // 避免不必要的交换  int temp = nums[left];  nums[left] = nums[right];  nums[right] = temp; } left++; // 左指针右移 } right++; // 右指针右移 } }}

Python

class Solution: def moveZeroes(self, nums: List[int]) -> None: \"\"\" Do not return anything, modify nums in-place instead. \"\"\" n = len(nums) left = right = 0 while right < n: if nums[right] != 0: if left != right: # 避免不必要的交换  nums[left], nums[right] = nums[right], nums[left] left += 1 # 左指针右移 right += 1 # 右指针右移

4、复杂度分析

• 时间复杂度为 O(n)
• 空间复杂度为 O(1)

Q5、盛最多水的容器

1、题目描述

给定一个长度为 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

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

2、解题思路

1. 双指针法：

   • 初始化：设置两个指针 left 和 right，分别指向数组的开始和末尾。
   • 计算面积：在每一步计算当前指针所指向的两条垂线构成的容器的面积，即 min(height[left], height[right]) * (right - left)。
   • 移动指针：比较 height[left] 和 height[right]，移动较小高度的指针，因为较大的高度可能带来更大的面积。
   • 更新最大值：在每一步计算后，更新记录的最大面积。

2. 优化操作：

   • 通过双指针法，可以确保在 O(n) 的时间内找到最大面积，避免了暴力解法的 O(n^2) 时间复杂度。
   • 每次移动指针都朝着可能增大的方向前进，确保了算法的效率。

3、代码实现

C++

class Solution {public: int maxArea(vector& height) { int left = 0, right = height.size() - 1; int ret = 0; while (left < right) { int Area = min(height[left], height[right]) * (right - left); ret = max(ret, Area); // 移动指针 if (height[left] < height[right]) { left++; } else { right--; } } return ret; }};

Java

class Solution { public int maxArea(int[] height) { int left = 0, right = height.length - 1; int ret = 0; while (left < right) { int Area = Math.min(height[left], height[right]) * (right - left); ret = Math.max(ret, Area); // 移动指针 if (height[left] < height[right]) { left++; } else { right--; } } return ret; }}

Python

class Solution: def maxArea(self, height: List[int]) -> int: left, right = 0, len(height) - 1 ret = 0 while left < right: Area = min(height[left], height[right]) * (right - left) ret = max(ret, Area) # 移动指针 if height[left] < height[right]: left += 1 else: right -= 1 return ret

4、复杂度分析

• 时间复杂度为 O(n)
• 空间复杂度为 O(1)

Q6、三数之和

1、题目描述

给你一个整数数组 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 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

2、解题思路

1. 排序数组：首先对数组进行排序，这样可以方便地使用双指针法来寻找满足条件的三元组。
2. 固定一个数：遍历数组，固定一个数 nums[i]，然后在剩下的数组中使用双指针法寻找另外两个数 nums[left] 和 nums[right]，使得它们的和等于 -nums[i]。
3. 双指针法 ：设置 left = i + 1 和 right = n - 1 ，计算 nums[left] + nums[right] 的和：
   • 如果和大于 -nums[i]，则 right--（因为数组已排序，右边的数较大）。
   • 如果和小于 -nums[i]，则 left++。
   • 如果和等于 -nums[i]，则记录这个三元组，并移动指针跳过重复元素。
4. 跳过重复元素：为了避免重复的三元组，需要在找到符合条件的组合后，跳过所有相同的 nums[left] 和 nums[right]，以及在固定 nums[i] 时跳过相同的 nums[i]。

3、代码实现

C++

class Solution {public: vector<vector> threeSum(vector& nums) { int n = nums.size(); sort(nums.begin(), nums.end()); vector<vector> ret; for (int i = 0; i  0 && nums[i] == nums[i - 1]) { continue; } int target = -nums[i]; int left = i + 1; int right = n - 1; while (left  target) {  --right; } else if (sum < target) {  left++; } else {  ret.push_back({nums[i], nums[left], nums[right]});  ++left;  --right;  // 跳过重复的 nums[left] 和 nums[right]  while (left < right && nums[left] == nums[left - 1]) { ++left;  }  while (left < right && nums[right] == nums[right + 1]) { --right;  } } } } return ret; }};

Java

class Solution { public List<List<Integer>> threeSum(int[] nums) { int n = nums.length; Arrays.sort(nums); List<List<Integer>> ret = new ArrayList<>(); for (int i = 0; i < n - 2; i++) { // 跳过重复的 nums[i] if (i > 0 && nums[i] == nums[i - 1]) { continue; } int target = -nums[i]; int left = i + 1; int right = n - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum > target) {  right--; } else if (sum < target) {  left++; } else {  ret.add(Arrays.asList(nums[i], nums[left], nums[right]));  left++;  right--;  // 跳过重复的 nums[left] 和 nums[right]  while (left < right && nums[left] == nums[left - 1]) { left++;  }  while (left < right && nums[right] == nums[right + 1]) { right--;  } } } } return ret; }}

Python

class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: n = len(nums) nums.sort() ret = [] for i in range(n - 2): # 跳过重复的 nums[i] if i > 0 and nums[i] == nums[i - 1]: continue target = -nums[i] left, right = i + 1, n - 1 while left < right: sum_ = nums[left] + nums[right] if sum_ > target:  right -= 1 elif sum_ < target:  left += 1 else:  ret.append([nums[i], nums[left], nums[right]])  left += 1  right -= 1  # 跳过重复的 nums[left] 和 nums[right]  while left < right and nums[left] == nums[left - 1]: left += 1  while left < right and nums[right] == nums[right + 1]: right -= 1 return ret

4、复杂度分析

• 时间复杂度为 O(n²)
• 空间复杂度为 O(1)

Q7、接雨水

1、题目描述

给定 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

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

2、解题思路

方法一：动态规划法（前缀/后缀最大值）

1. 核心思想：对于每个柱子，其能接的雨水量等于左右两边最高柱子中的较小值减去当前柱子的高度。
2. 实现步骤 ：
   • 从左到右计算每个位置的左边最大值
   • 从右到左计算每个位置的右边最大值
   • 遍历数组，计算每个位置能接的雨水量（左右最大值中的较小值减去当前高度）

方法二：单调栈法

1. 核心思想：使用栈来跟踪可能形成\"凹槽\"的柱子，当遇到比栈顶高的柱子时，计算可以接的雨水量。
2. 实现步骤 ：
   • 维护一个单调递减栈
   • 当遇到比栈顶高的柱子时，弹出栈顶作为底部，计算当前柱子与新的栈顶形成的凹槽能接的雨水量
   • 重复这个过程直到栈顶柱子比当前柱子高或栈为空

方法三：双指针法

1. 核心思想：使用两个指针从两端向中间移动，动态维护左右两边的最大值，根据较小的一边计算当前柱子的接水量。

2. 实现步骤 ：

   • 初始化左右指针和左右最大值
   • 移动较小高度的指针
   • 计算当前指针位置的接水量（当前侧的最大值减去当前高度）

3、代码实现

C++

// 方法1: 动态规划法class Solution {public: int trap(vector& height) { int n = height.size(); if (n == 0) { return 0; } // 1. 计算每个位置左边的最大值 vector leftMax(n); leftMax[0] = height[0]; // 第一个元素的左边最大值就是它自己 for (int i = 1; i < n; ++i) { leftMax[i] = max(leftMax[i - 1], height[i]); } // 2. 计算每个位置右边的最大值 vector rightMax(n); rightMax[n - 1] = height[n - 1]; // 最后一个元素的右边最大值就是它自己 for (int i = n - 2; i >= 0; --i) { rightMax[i] = max(rightMax[i + 1], height[i]); } // 3. 计算每个位置能接的雨水量 int ret = 0; for (int i = 0; i < n; ++i) { // 当前柱子的接水量 = min(左边最高, 右边最高) - 当前高度 ret += min(leftMax[i], rightMax[i]) - height[i]; } return ret; }};

// 方法2: 单调栈法class Solution {public: int trap(vector& height) { int ret = 0; stack stk; // 维护一个单调递减栈 int n = height.size(); for (int i = 0; i  height[stk.top()]) { int top = stk.top(); // 凹槽的底部 stk.pop(); if (stk.empty()) {  break; // 没有左边界, 无法形成凹槽 } int left = stk.top(); // 左边界 int curWidth = i - left - 1; // 凹槽的宽度 int curHeight = min(height[left], height[i]) - height[top]; // 凹槽的高度 ret += curWidth * curHeight; // 计算当前凹槽的接水量 } stk.push(i); // 将当前柱子压入栈 } return ret; }};

// 方法3: 双指针法class Solution {public: int trap(vector& height) { int ret = 0; int left = 0, right = height.size() - 1; // 初始化双指针 int leftMax = 0, rightMax = 0;  // 记录左右两边的最大值 while (left < right) { // 更新左右两边的最大值 leftMax = max(leftMax, height[left]); rightMax = max(rightMax, height[right]); if (height[left] < height[right]) { // 左边柱子较矮, 计算左边柱子的接水量 ret += leftMax - height[left]; ++left; // 移动左指针 } else { // 右边柱子较矮, 计算右边柱子的接水量 ret += rightMax - height[right]; --right; // 移动右指针 } } return ret; }};

Java

// 方法1: 动态规划法class Solution { public int trap(int[] height) { int n = height.length; if (n == 0) return 0; int[] leftMax = new int[n]; int[] rightMax = new int[n]; leftMax[0] = height[0]; for (int i = 1; i < n; i++) { leftMax[i] = Math.max(leftMax[i-1], height[i]); } rightMax[n-1] = height[n-1]; for (int i = n-2; i >= 0; i--) { rightMax[i] = Math.max(rightMax[i+1], height[i]); } int res = 0; for (int i = 0; i < n; i++) { res += Math.min(leftMax[i], rightMax[i]) - height[i]; } return res; }}

// 方法2: 单调栈法class Solution { public int trap(int[] height) { Stack stack = new Stack(); int res = 0, i = 0, n = height.length; while (i  height[stack.peek()]) { int top = stack.pop(); if (stack.isEmpty()) {  break; } int distance = i - stack.peek() - 1; int bounded_height = Math.min(height[i], height[stack.peek()]) - height[top]; res += distance * bounded_height; } stack.push(i++); } return res; }}

// 方法3: 双指针法class Solution { public int trap(int[] height) { int left = 0, right = height.length - 1; int left_max = 0, right_max = 0; int res = 0; while (left < right) { if (height[left] = left_max) {  left_max = height[left]; } else {  res += left_max - height[left]; } left++; } else { if (height[right] >= right_max) {  right_max = height[right]; } else {  res += right_max - height[right]; } right--; } } return res; }}

Python

# 方法1: 动态规划法class Solution: def trap(self, height: List[int]) -> int: if not height: return 0 n = len(height) left_max = [0] * n right_max = [0] * n left_max[0] = height[0] for i in range(1, n): left_max[i] = max(left_max[i-1], height[i]) right_max[-1] = height[-1] for i in range(n-2, -1, -1): right_max[i] = max(right_max[i+1], height[i]) res = 0 for i in range(n): res += min(left_max[i], right_max[i]) - height[i] return res

# 方法2: 单调栈法class Solution: def trap(self, height: List[int]) -> int: stack = [] res = 0 i = 0 n = len(height) while i  height[stack[-1]]: top = stack.pop() if not stack:  break distance = i - stack[-1] - 1 bounded_height = min(height[i], height[stack[-1]]) - height[top] res += distance * bounded_height stack.append(i) i += 1 return res

# 方法3: 双指针法class Solution: def trap(self, height: List[int]) -> int: left, right = 0, len(height) - 1 left_max = right_max = 0 res = 0 while left < right: if height[left] = left_max:  left_max = height[left] else:  res += left_max - height[left] left += 1 else: if height[right] >= right_max:  right_max = height[right] else:  res += right_max - height[right] right -= 1 return res

4、复杂度分析

方法 时间复杂度 空间复杂度 适用场景 动态规划 O(n) O(n) 通用解法，较易理解 单调栈 O(n) O(n) 适合理解栈的应用 双指针 O(n) O(1) 最优空间复杂度解法

3、滑动窗口

Q8、无重复字符的最长子串

1、题目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

2、解题思路

滑动窗口法是最优解决方案：

1. 使用哈希表记录字符最后出现的位置
2. 维护一个滑动窗口，窗口内保证没有重复字符
3. 当遇到重复字符时，移动左边界到重复字符的下一个位置
4. 不断更新最大窗口大小

3、代码实现

C++

class Solution {public: int lengthOfLongestSubstring(string s) { int hash[128] = {0}; // 使用数组模拟哈希表, 记录字符出现次数 int left = 0, right = 0; // 滑动窗口的左右边界 int n = s.size(); int max_len = 0; // 记录最大长度 while (right  1) { hash[s[left++]]--; // 移除左边界字符, 并移动左边界 } ++right; // 移动右边界 max_len = max(max_len, right - left); // 更新最大长度 } return max_len; }};

Java

class Solution { public int lengthOfLongestSubstring(String s) { int[] hash = new int[128]; // ASCII码表大小 int left = 0, right = 0; int maxLen = 0; while (right < s.length()) { char c = s.charAt(right); hash[c]++; // 当发现重复字符时，收缩窗口 while (hash[c] > 1) { char leftChar = s.charAt(left); hash[leftChar]--; left++; } right++; maxLen = Math.max(maxLen, right - left); } return maxLen; }}

Python

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: hash_map = [0] * 128 # ASCII码表大小 left = right = 0 max_len = 0 while right < len(s): hash_map[ord(s[right])] += 1 # 当前字符进入窗口 # 当发现重复字符时，收缩窗口 while hash_map[ord(s[right])] > 1: hash_map[ord(s[left])] -= 1 left += 1 right += 1 max_len = max(max_len, right - left)  return max_len

4、复杂度分析

• 时间复杂度：O(n)，只需遍历一次字符串
• 空间复杂度：O(1)，使用固定大小的数组作为哈希表

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

1、题目描述

给定两个字符串 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\" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

2、解题思路

1. 使用哈希表统计 p 中每个字符的出现次数
2. 维护一个与 p 长度相同的滑动窗口
3. 统计窗口中字符出现次数并与 p 的统计结果比较
4. 当窗口内字符计数与 p 完全匹配时，记录起始索引

3、代码实现

C++

class Solution {public: vector findAnagrams(string s, string p) { vector result; if (s.size() < p.size()) { return result; } int hash1[26] = {0}; // 统计 p 中各字符出现次数 int hash2[26] = {0}; // 统计窗口内各字符出现次数 int m = p.size(); // 目标字符串长度 // 初始化 p 的哈希表 for (char ch : p) { hash1[ch - \'a\']++; } int left = 0, count = 0; for (int right = 0; right < s.size(); ++right) { // 当前字符进入窗口 char inChar = s[right]; hash2[inChar - \'a\']++; // 如果当前字符在 p 中存在且未超过出现次数, 增加有效计数 if (hash2[inChar - \'a\']  m) { char outChar = s[left]; // 如果移出的字符在 p 中存在且未超过出现次数, 减少有效计数 if (hash2[outChar - \'a\'] <= hash1[outChar - \'a\']) {  count--; } hash2[outChar - \'a\']--; left++; } // 当有效计数等于 p 的长度时, 找到异位词 if (count == m) { result.push_back(left); } } return result; }};

Java

class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> result = new ArrayList<>(); if (s.length() < p.length()) { return result; } int[] hash1 = new int[26]; // 统计p的字符频率 int[] hash2 = new int[26]; // 统计窗口的字符频率 int m = p.length(); // 初始化p的哈希表 for (char ch : p.toCharArray()) { hash1[ch - \'a\']++; } int left = 0, count = 0; for (int right = 0; right < s.length(); right++) { char inChar = s.charAt(right); hash2[inChar - \'a\']++; // 有效字符计数 if (hash2[inChar - \'a\'] <= hash1[inChar - \'a\']) { count++; } // 窗口大小超过p长度时移动左边界 if (right - left + 1 > m) { char outChar = s.charAt(left); if (hash2[outChar - \'a\'] <= hash1[outChar - \'a\']) {  count--; } hash2[outChar - \'a\']--; left++; } // 找到异位词 if (count == m) { result.add(left); } } return result; }}

Python

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: result = [] if len(s) < len(p): return result hash1 = [0] * 26 # 统计p的字符频率 hash2 = [0] * 26 # 统计窗口的字符频率 m = len(p) # 初始化p的哈希表 for ch in p: hash1[ord(ch) - ord(\'a\')] += 1 left = count = 0 for right in range(len(s)): # 当前字符进入窗口 in_char = s[right] hash2[ord(in_char) - ord(\'a\')] += 1 # 有效字符计数 if hash2[ord(in_char) - ord(\'a\')] <= hash1[ord(in_char) - ord(\'a\')]: count += 1 # 窗口大小超过p长度时移动左边界 if right - left + 1 > m: out_char = s[left] if hash2[ord(out_char) - ord(\'a\')] <= hash1[ord(out_char) - ord(\'a\')]:  count -= 1 hash2[ord(out_char) - ord(\'a\')] -= 1 left += 1 # 找到异位词 if count == m: result.append(left) return result

4、复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度
• 空间复杂度：O(1)，使用固定大小的数组作为哈希表

4、子串

Q10、和为 K 的子数组

1、题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

2、解题思路

1. 暴力枚举法：枚举所有可能的子数组，计算它们的和 （超时）
2. 前缀和+哈希表优化法：利用前缀和和哈希表来优化查找过程

3、代码实现

C++

class Solution {public: int subarraySum(vector& nums, int k) { unordered_map hash; // 存储前缀和以及其出现次数 hash[0] = 1;  // 初始状况, 前缀和为 0 出现 1 次 int sum = 0, ret = 0; for (const auto& num : nums) { sum += num; // 计算当前前缀和 // 如果存在前缀和等于 sum - k, 说明中间有子数组和为 k if (hash.count(sum - k)) { ret += hash[sum - k]; // 累加符合条件的子数组数量 } hash[sum]++; // 记录当前前缀和 } return ret; }};

Java

class Solution { public int subarraySum(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); map.put(0, 1); // 初始状态，前缀和为0出现1次 int sum = 0, count = 0; for (int num : nums) { sum += num; if (map.containsKey(sum - k)) { count += map.get(sum - k); } map.put(sum, map.getOrDefault(sum, 0) + 1); } return count; }}

Python

class Solution: def subarraySum(self, nums: List[int], k: int) -> int: prefix_sum = {0: 1} # 初始状态，前缀和为0出现1次 sum_ = 0 count = 0 for num in nums: sum_ += num # 如果sum_-k存在，说明有子数组和为k if (sum_ - k) in prefix_sum: count += prefix_sum[sum_ - k] # 记录当前前缀和 prefix_sum[sum_] = prefix_sum.get(sum_, 0) + 1 return count

4、复杂度分析

暴力枚举法

• 时间复杂度：O(n²)，双层循环遍历所有子数组
• 空间复杂度：O(1)，仅使用常数空间

前缀和+哈希表优化法

• 时间复杂度：O(n)，只需一次遍历
• 空间复杂度：O(n)，需要存储前缀和的哈希表

Q11、滑动窗口最大值

1、题目描述

给你一个整数数组 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]

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

2、解题思路

方法一：暴力法（不可取）

最直观的方法是对于每个窗口，遍历其中的 k 个元素找到最大值。虽然简单，但时间复杂度为O(nk)，对于大数组会超时。

方法二：优先队列/最大堆

核心思想：

• 使用堆来维护当前窗口中的元素，堆顶即为最大值
• 需要处理堆中元素可能不在当前窗口的情况

具体步骤：

1. 初始化：将前 k 个元素加入最大堆（存储值和索引）
2. 第一个窗口的最大值即为堆顶元素
3. 滑动窗口：
   • 加入新元素到堆中
   • 检查堆顶元素是否在当前窗口内（通过索引判断）
   • 如果不在，则弹出堆顶元素，直到找到在当前窗口的最大值

复杂度分析：

• 时间复杂度：O(nlogn)，每个元素最多进出堆一次
• 空间复杂度：O(n)，堆的大小

方法三：单调队列（最优解）

核心思想：

• 维护一个双端队列，队列中的元素索引对应的数组值单调递减
• 队列头部始终是当前窗口的最大值

具体步骤：

1. 初始化队列：处理第一个窗口
   • 对于每个新元素，从队列尾部移除比它小的元素
   • 将当前元素索引加入队列
2. 记录第一个窗口的最大值（队列头部）
3. 滑动窗口：
   • 加入新元素：同样从队列尾部移除比它小的元素
   • 检查队列头部元素是否还在窗口内，不在则移除
   • 当前窗口的最大值即为新的队列头部

为什么有效：

1. 单调性保证：队列中元素对应的值递减，所以头部总是最大值
2. 及时淘汰：新元素比队列中某些元素大时，这些元素不再可能是后续窗口的最大值
3. 窗口维护：通过索引检查确保队列头部在窗口内

3、代码实现

C++

// 方法1: 优先队列法class Solution {public: vector maxSlidingWindow(vector& nums, int k) { int n = nums.size(); // 优先队列存储值和索引, 按值降序排列 priority_queue<pair> q; // 初始化前 k 个元素 for (int i = 0; i < k; ++i) { q.emplace(nums[i], i); } vector ret = {q.top().first}; for (int i = k; i < n; ++i) { q.emplace(nums[i], i); // 加入新元素 // 移除不在当前窗口的最大值 while (q.top().second <= i - k) { q.pop(); } ret.push_back(q.top().first); } return ret; }};

// 方法二: 单调队列法class Solution {public: vector maxSlidingWindow(vector& nums, int k) { int n = nums.size(); deque q; // 存储索引, 对应的 nums 值单调递减 // 初始化第一个窗口 for (int i = 0; i = nums[q.back()]) { q.pop_back(); } q.push_back(i); } vector ret = {nums[q.front()]}; for (int i = k; i = nums[q.back()]) { q.pop_back(); } q.push_back(i); // 移除不在窗口内的元素 while (q.front() <= i - k) { q.pop_front(); } ret.push_back(nums[q.front()]); } return ret; }};

Java

// 方法1: 优先队列法class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; // 优先队列存储值和索引，按值降序排列 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]); // 初始化前k个元素 for (int i = 0; i < k; i++) { pq.offer(new int[] { nums[i], i }); } int[] ret = new int[n - k + 1]; ret[0] = pq.peek()[0]; for (int i = k; i < n; i++) { pq.offer(new int[] { nums[i], i }); // 加入新元素 // 移除不在当前窗口的最大值 while (pq.peek()[1] <= i - k) { pq.poll(); } ret[i - k + 1] = pq.peek()[0]; } return ret; }}

// 方法二：单调队列法class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; Deque q = new ArrayDeque(); // 存储索引，对应的nums值单调递减 int[] ret = new int[n - k + 1]; // 初始化第一个窗口 for (int i = 0; i = nums[q.peekLast()]) { q.pollLast(); } q.offerLast(i); } ret[0] = nums[q.peekFirst()]; for (int i = k; i = nums[q.peekLast()]) { q.pollLast(); } q.offerLast(i); // 移除不在窗口内的元素 while (q.peekFirst() <= i - k) { q.pollFirst(); } ret[i - k + 1] = nums[q.peekFirst()]; } return ret; }}

Python

# 方法一：优先队列法class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) # 优先队列存储(-值, 索引)模拟最大堆 heap = [] for i in range(k): heapq.heappush(heap, (-nums[i], i)) res = [-heap[0][0]] for i in range(k, n): heapq.heappush(heap, (-nums[i], i)) # 移除不在当前窗口的最大值 while heap[0][1] <= i - k: heapq.heappop(heap) res.append(-heap[0][0]) return res

# 方法二：单调队列法class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: q = deque() # 存储索引，对应的nums值单调递减 res = [] # 初始化第一个窗口 for i in range(k): while q and nums[i] >= nums[q[-1]]: q.pop() q.append(i) res.append(nums[q[0]]) for i in range(k, len(nums)): # 维护单调递减性质 while q and nums[i] >= nums[q[-1]]: q.pop() q.append(i) # 移除不在窗口内的元素 while q[0] <= i - k: q.popleft() res.append(nums[q[0]]) return res

4、复杂度分析

方法 时间复杂度 空间复杂度 适用场景 暴力法 O(nk) O(1) 小数据集 优先队列法 O(nlogn) O(n) 中等规模数据 单调队列法 O(n) O(k) 大规模数据（最优）

Q12、最小覆盖子串

1、题目描述

给你一个字符串 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 的子串中，因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s 和 t 由英文字母组成

**进阶：**你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

2、解题思路

1. 统计目标字符频率：首先统计字符串t中每个字符的出现次数
2. 滑动窗口遍历：使用双指针left和right维护一个窗口
3. 窗口扩展：右指针right向右移动，包含新字符
4. 窗口收缩：当窗口包含所有t的字符时，左指针left向右移动寻找最小窗口
5. 更新结果：每次满足条件时记录当前最小窗口

3、代码实现

C++

class Solution {public: string minWindow(string s, string t) { // 统计 t 中字符出现次数 int hash1[128] = {0}; int kinds = 0; // t 中不同字符的种类数 for (const auto& ch : t) { if (hash1[ch]++ == 0) { kinds++; } } int hash2[128] = {0}; // 统计当前窗口中字符出现次数 int begin = -1, minlen = INT_MAX; // 记录最小窗口的起始位置和长度 // 滑动窗口遍历 for (int left = 0, right = 0, count = 0; right < s.size(); ++right) { char in = s[right]; // 新进入窗口的字符 // 更新当前窗口字符计数 if (++hash2[in] == hash1[in]) { count++; // 当某个字符数量达到 t 中要求时增加 count } // 当窗口包含所有 t 的字符时, 尝试收缩窗口 while (count == kinds) { // 更新最小窗口 if (right - left + 1 < minlen) {  minlen = right - left + 1;  begin = left; } char out = s[left++]; // 移除窗口的字符 // 更新窗口字符计数 if (hash2[out]-- == hash1[out]) {  count--; // 如果移出的字符是 t 中需要的, 减少 count } } } return begin == -1 ? \"\" : s.substr(begin, minlen); }};

Java

class Solution { public String minWindow(String s, String t) { int[] hash1 = new int[128]; // 存储t中字符频率 int kinds = 0; // t中不同字符的种类数 for (char ch : t.toCharArray()) { if (hash1[ch]++ == 0) { kinds++; } } int[] hash2 = new int[128]; // 存储当前窗口字符频率 int begin = -1, minlen = Integer.MAX_VALUE; // 记录最小窗口位置和长度 for (int left = 0, right = 0, count = 0; right < s.length(); right++) { char in = s.charAt(right); if (++hash2[in] == hash1[in]) { count++; // 字符计数达到要求时增加count } while (count == kinds) { // 窗口包含所有t的字符时 if (right - left + 1 < minlen) { // 更新最小窗口  minlen = right - left + 1;  begin = left; } char out = s.charAt(left++); if (hash2[out]-- == hash1[out]) {  count--; // 移出字符时减少count } } } return begin == -1 ? \"\" : s.substring(begin, begin + minlen); }}

Python

class Solution: def minWindow(self, s: str, t: str) -> str: hash1 = [0] * 128 # 存储t中字符频率 kinds = 0 # t中不同字符的种类数 for ch in t: if hash1[ord(ch)] == 0: kinds += 1 hash1[ord(ch)] += 1 hash2 = [0] * 128 # 存储当前窗口字符频率 begin, minlen = -1, float(\'inf\') # 记录最小窗口位置和长度 left = count = 0 for right in range(len(s)): in_ch = s[right] hash2[ord(in_ch)] += 1 if hash2[ord(in_ch)] == hash1[ord(in_ch)]: count += 1 # 字符计数达到要求时增加count while count == kinds: # 窗口包含所有t的字符时 if right - left + 1 < minlen: # 更新最小窗口  minlen = right - left + 1  begin = left out_ch = s[left] left += 1 hash2[ord(out_ch)] -= 1 if hash2[ord(out_ch)] < hash1[ord(out_ch)]:  count -= 1 # 移出字符时减少count return \"\" if begin == -1 else s[begin:begin+minlen]

4、复杂度分析

• 时间复杂度：O(n)，其中n是字符串s的长度，每个字符最多被访问两次（右指针和左指针各一次）
• 空间复杂度：O(1)，使用固定大小的哈希表（128个ASCII字符）

5、普通数组

Q13、最大子数组和

1、题目描述

给你一个整数数组 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

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

2、解题思路

方法一：动态规划

1. 状态定义：dp[i] 表示以 nums[i-1] 结尾的子数组的最大和
2. 状态转移方程 ：
   • dp[i] = max(nums[i-1], dp[i-1] + nums[i-1])
3. 初始化：dp[0] = 0
4. 结果：max(dp[1…n])

方法二：Kadane算法（优化空间）

1. 思路：只需要知道前一个状态的最大和，不需要存储整个dp数组
2. 变量 ：
   • curSum：当前子数组和
   • maxSum：全局最大和
3. 更新规则 ：
   • curSum = max(num, curSum + num)
   • maxSum = max(maxSum, curSum)

方法三：分治法（进阶）

1. 分：将数组分成左右两部分
2. 治：递归求解左右两部分的最大子数组和
3. 合：计算跨越中间的最大子数组和，取三者最大值

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int maxSubArray(vector& nums) { int n = nums.size(); vector dp(n + 1, 0); // dp[i] 表示以 nums[i-1] 结尾的最大子数组和 int ret = INT_MIN; for (int i = 1; i <= n; ++i) { dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]); // 状态转移 ret = max(ret, dp[i]); // 更新全局最大值 } return ret; }};

// 方法2: Kadaneclass Solution {public: int maxSubArray(vector& nums) { int maxSum = INT_MIN, curSum = 0; for (const auto& num : nums) { curSum = max(num, curSum + num); // 决定是重新开始还是继续累加 maxSum = max(maxSum, curSum); // 更新全局最大值 } return maxSum; }};

// 方法3: 分治法class Solution {public: int maxSubArray(vector& nums) { return divide(nums, 0, nums.size() - 1); } int divide(vector& nums, int left, int right) { if (left == right) { return nums[left]; } int mid = left + (right - left) / 2; int leftMax = divide(nums, left, mid);  // 左半部分最大值 int rightMax = divide(nums, mid + 1, right); // 右半部分最大值 int crossMax = crossSum(nums, left, right, mid); // 跨越中间的最大值 return max({leftMax, rightMax, crossMax}); } int crossSum(vector& nums, int left, int right, int mid) { int leftSum = INT_MIN, sum = 0; for (int i = mid; i >= left; --i) { sum += nums[i]; leftSum = max(leftSum, sum); } int righSum = INT_MIN; sum = 0; for (int i = mid + 1; i <= right; ++i) { sum += nums[i]; righSum = max(righSum, sum); } return leftSum + righSum; }};

Java

// 方法2: Kadaneclass Solution { public int maxSubArray(int[] nums) { int maxSum = Integer.MIN_VALUE, curSum = 0; for (int num : nums) { curSum = Math.max(num, curSum + num); maxSum = Math.max(maxSum, curSum); } return maxSum; }}

Python

# 方法2: Kadaneclass Solution: def maxSubArray(self, nums: List[int]) -> int: max_sum = cur_sum = float(\'-inf\') for num in nums: cur_sum = max(num, cur_sum + num) max_sum = max(max_sum, cur_sum) return max_sum

4、复杂度分析

• 方法一：时间O(n)，空间O(n)
• 方法二：时间O(n)，空间O(1)
• 方法三：时间O(nlogn)，空间O(logn)

Q14、合并区间

1、题目描述

以数组 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] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

2、解题思路

1. 排序区间：首先将所有区间按照起始位置进行排序
2. 初始化结果集：创建一个空列表用于存储合并后的区间
3. 遍历并合并 ：
   • 如果结果集为空或者当前区间与结果集中最后一个区间不重叠，直接加入结果集
   • 否则，合并当前区间与结果集中最后一个区间，取两者的最大结束位置

3、代码实现

C++

class Solution {public: vector<vector> merge(vector<vector>& intervals) { // 如果区间为空, 直接返回空数组 if (intervals.empty()) { return {}; } // 按区间起始位置排序 sort(intervals.begin(), intervals.end()); vector<vector> merged; // 存储合并后的结果 for (const auto& interval : intervals) { // 如果结果为空或当前区间与最后一个区间不重叠, 直接添加 if (merged.empty() || merged.back()[1] < interval[0]) { merged.push_back(interval); } // 否则合并区间, 取最大的结束位置 else { merged.back()[1] = max(merged.back()[1], interval[1]); } } return merged; }};

Java

class Solution { public int[][] merge(int[][] intervals) { // 如果区间为空，直接返回空数组 if (intervals.length == 0) { return new int[0][2]; } // 按区间起始位置排序 Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); List<int[]> merged = new ArrayList<>(); // 存储合并后的结果 for (int[] interval : intervals) { // 如果结果为空或当前区间与最后一个区间不重叠，直接添加 if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) { merged.add(interval); } // 否则合并区间，取最大的结束位置 else { merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]); } } return merged.toArray(new int[merged.size()][]); }}

Python

class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: # 如果区间为空，直接返回空列表 if not intervals: return [] # 按区间起始位置排序 intervals.sort(key=lambda x: x[0]) merged = [] # 存储合并后的结果 for interval in intervals: # 如果结果为空或当前区间与最后一个区间不重叠，直接添加 if not merged or merged[-1][1] < interval[0]: merged.append(interval) # 否则合并区间，取最大的结束位置 else: merged[-1][1] = max(merged[-1][1], interval[1]) return merged

4、复杂度分析

• 时间复杂度：O(nlogn)，主要是排序的时间复杂度
• 空间复杂度：O(logn)，排序所需的栈空间

Q15、轮转数组

1、题目描述

给定一个整数数组 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]

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

进阶：

• 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
• 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

2、解题思路

方法一：使用额外数组

1. 创建一个新数组
2. 将原数组中的元素放到新数组的正确位置：(i + k) % n
3. 将新数组复制回原数组

方法二：环状替换

1. 计算实际需要移动的步数 k = k % n
2. 使用最大公约数确定需要多少轮替换
3. 每轮中循环替换元素直到回到起始位置

方法三：三次反转

1. 反转整个数组
2. 反转前k个元素
3. 反转剩下的元素

3、代码实现

C++

// 方法1: 使用额外数组class Solution {public: void rotate(vector& nums, int k) { int n = nums.size(); vector newArr(n); for (int i = 0; i < n; ++i) { newArr[(i + k) % n] = nums[i]; // 计算新位置 } nums.assign(newArr.begin(), newArr.end()); // 复制回原数组 }};

// 方法2: 换装替换class Solution {public: void rotate(vector& nums, int k) { int n = nums.size(); k = k % n; // 处理 k 大于 n 的情况 int count = gcd(k, n); // 计算需要多少轮替换 for (int start = 0; start < count; ++start) { int current = start; int prev = nums[start]; // 保存起始元素 do { int next = (current + k) % n; // 计算下一个位置 swap(nums[next], prev); // 交换元素 current = next;  // 移动到下一个位置 } while (start != current); // 直到回到起始位置 } }};

// 方法3: 三次反转class Solution {public: void rotate(vector& nums, int k) { k %= nums.size();  // 处理 k 大于数组长度的情况 reverse(nums, 0, nums.size() - 1); // 反转整个数组 reverse(nums, 0, k - 1);  // 反转前 k 个元素 reverse(nums, k, nums.size() - 1); // 反转剩余元素 } void reverse(vector& nums, int start, int end) { while (start < end) { swap(nums[start], nums[end]); // 交换元素 start++; end--; } }};

Java

// 方法3: 三次反转class Solution { public void rotate(int[] nums, int k) { k %= nums.length; reverse(nums, 0, nums.length - 1); reverse(nums, 0, k - 1); reverse(nums, k, nums.length - 1); } private void reverse(int[] nums, int start, int end) { while (start < end) { int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start++; end--; } }}

Python

# 方法3: 三次反转class Solution: def rotate(self, nums: List[int], k: int) -> None: \"\"\" Do not return anything, modify nums in-place instead. \"\"\" k %= len(nums) self.reverse(nums, 0, len(nums)-1) self.reverse(nums, 0, k-1) self.reverse(nums, k, len(nums)-1) def reverse(self, nums: List[int], start: int, end: int) -> None: while start < end: nums[start], nums[end] = nums[end], nums[start] start += 1 end -= 1

4、复杂度分析

方法 时间复杂度 空间复杂度 额外数组 O(n) O(n) 环状替换 O(n) O(1) 三次反转 O(n) O(1)

Q16、除自身以外数组的乘积

1、题目描述

给你一个整数数组 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]

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 输入 保证 数组 answer[i] 在 32 位 整数范围内

**进阶：**你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

2、解题思路

方法一：左右乘积数组

1. 计算左乘积：从左到右遍历，计算每个元素左侧所有元素的乘积
2. 计算右乘积：从右到左遍历，计算每个元素右侧所有元素的乘积
3. 结果计算：将左右乘积相乘得到最终结果

方法二：空间优化（O(1)）

1. 初始结果数组：将结果数组初始化为1
2. 左乘积计算：从左到右遍历，用变量记录左乘积并更新结果数组
3. 右乘积计算：从右到左遍历，用变量记录右乘积并更新结果数组

3、代码实现

C++

// 方法1: 左右乘积数组class Solution {public: vector productExceptSelf(vector& nums) { int n = nums.size(); vector left(n, 1), right(n, 1), answer(n); // 计算左右乘积数组 for (int i = 1; i = 0; --i) { right[i] = right[i + 1] * nums[i + 1]; } // 计算最终结果 for (int i = 0; i < n; ++i) { answer[i] = left[i] * right[i]; } return answer; }};

// 方法2: 空间优化class Solution {public: vector productExceptSelf(vector& nums) { int n = nums.size(); vector answer(n, 1); int left = 1; // 初始化左乘积 for (int i = 0; i = 0; --i) { answer[i] *= right; // 更新结果数组 right *= nums[i]; // 更新右乘积 } return answer; }};

Java

class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] answer = new int[n]; Arrays.fill(answer, 1); int left = 1; for (int i = 0; i < n; i++) { answer[i] *= left; left *= nums[i]; } int right = 1; for (int i = n - 1; i >= 0; i--) { answer[i] *= right; right *= nums[i]; } return answer; }}

Python

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) answer = [1] * n left = 1 for i in range(n): answer[i] *= left left *= nums[i] right = 1 for i in range(n-1, -1, -1): answer[i] *= right right *= nums[i] return answer

4、复杂度分析

方法 时间复杂度 空间复杂度 左右乘积数组 O(n) O(n) 空间优化 O(n) O(1)（不考虑输出数组）

Q17、缺失的第一个正数

1、题目描述

给你一个未排序的整数数组 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 没有出现。

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

2、解题思路

方法一：哈希标记法

1. 处理非正数：将所有非正数替换为 n+1（超出范围）
2. 标记存在的数：对于每个数，将其对应的位置标记为负数
3. 查找缺失的正数：第一个未被标记的位置对应的数就是缺失的最小正数

方法二：原地置换法

1. 原地排序：将每个数放到它应该在的位置（nums[i] = i+1）
2. 查找不符的数：第一个与位置不符的数就是缺失的最小正数

3、代码实现

C++

// 方法1: 哈希标记法class Solution {public: int firstMissingPositive(vector& nums) { int n = nums.size(); // 第一步: 将所有非正数替换为 n+1 for (int& num : nums) { if (num <= 0) { num = n + 1; } } // 第二步: 标记存在的数字对应的位置为负数 for (int i = 0; i < n; ++i) { int num = abs(nums[i]); // 取绝对值 // 如果在 1 到 n 范围内 if (num <= n) { nums[num - 1] = -abs(nums[num - 1]); // 标记对应位置为负 } } // 第三步: 找到第一个未被标记的位置 for (int i = 0; i  0) { return i + 1; // 返回对应的正数 } } // 如果 1 到 n 都出现了, 则返回 n+1 return n + 1; }};

// 方法2: 原地置换法class Solution {public: int firstMissingPositive(vector& nums) { int n = nums.size(); // 原地置换排序, 将每个数放到它应该在的位置 for (int i = 0; i  0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { swap(nums[nums[i] - 1], nums[i]); // 交换到正确位置 } } // 查找第一个不符合 nums[i] == i+1 的位置 for (int i = 0; i < n; ++i) { if (nums[i] != i + 1) { return i + 1; } } // 如果 1 到 n 都出现了, 则返回 n+1 return n + 1; }};

Java

class Solution { public int firstMissingPositive(int[] nums) { int n = nums.length; // 原地置换排序 for (int i = 0; i < n; ++i) { while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { swap(nums, nums[i] - 1, i); } } // 查找第一个不符合的位置 for (int i = 0; i < n; ++i) { if (nums[i] != i + 1) { return i + 1; } } return n + 1; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}

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[nums[i] - 1] != nums[i]: nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1] # 查找第一个不符合的位置 for i in range(n): if nums[i] != i + 1: return i + 1 return n + 1

4、复杂度分析

方法 时间复杂度 空间复杂度 哈希标记法 O(n) O(1) 原地置换法 O(n) O(1)

6、矩阵

Q18、矩阵置零

1、题目描述

给定一个 *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]]

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

进阶：

• 一个直观的解决方案是使用 O(*m**n*) 的额外空间，但这并不是一个好的解决方案。
• 一个简单的改进方案是使用 O(*m* + *n*) 的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个仅使用常量空间的解决方案吗？

2、解题思路

方法一：标记数组法

1. 创建标记数组：使用两个数组分别记录需要置零的行和列
2. 第一次遍历：标记所有 0 元素所在的行和列
3. 第二次遍历：根据标记数组将对应行和列置零

方法二：原地标记法（常数空间）

1. 标记第一行和第一列：使用第一行和第一列作为标记数组
2. 处理内部元素：从第二行第二列开始遍历，用第一行和第一列记录需要置零的行和列
3. 根据标记置零：根据第一行和第一列的标记将内部元素置零
4. 处理第一行和第一列：最后处理第一行和第一列是否需要置零

3、代码实现

C++

// 方法1: 标记数组法class Solution {public: void setZeroes(vector<vector>& matrix) { int m = matrix.size(); int n = matrix[0].size(); vector row(m, false), col(n, false); // 标记数组 // 第一遍遍历: 标记需要置零的行和列 for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (matrix[i][j] == 0) {  row[i] = true; // 标记行  col[j] = true; // 标记列 } } } // 第二次遍历: 根据标记置零 for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { // 如果行或者列被标记 if (row[i] || col[j]) {  matrix[i][j] = 0; // 置零 } } } }};

// 方法2: 原地标记法class Solution {public: void setZeroes(vector<vector>& matrix) { int m = matrix.size(); int n = matrix[0].size(); bool firstRowZero = false, firstColZero = false; // 检查第一列是否需要置零 for (int i = 0; i < m; ++i) { if (matrix[i][0] == 0) { firstColZero = true; break; } } // 检查第一行是否需要置零 for (int j = 0; j < n; ++j) { if (matrix[0][j] == 0) { firstRowZero = true; break; } } // 使用第一行和第一列作为标记 for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[i][j] == 0) {  matrix[i][0] = 0; // 标记行  matrix[0][j] = 0; // 标记列 } } } // 根据标记置零内部元素 for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[i][0] == 0 || matrix[0][j] == 0) {  matrix[i][j] = 0; } } } // 处理第一列 if (firstColZero) { for (int i = 0; i < m; ++i) { matrix[i][0] = 0; } } // 处理第一行 if (firstRowZero) { for (int j = 0; j < n; ++j) { matrix[0][j] = 0; } } }};

Java

// 方法2: 原地标记法class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; boolean firstRowZero = false, firstColZero = false; // 检查第一列是否需要置零 for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) { firstColZero = true; break; } } // 检查第一行是否需要置零 for (int j = 0; j < n; j++) { if (matrix[0][j] == 0) { firstRowZero = true; break; } } // 使用第一行和第一列作为标记 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) {  matrix[i][0] = 0;  matrix[0][j] = 0; } } } // 根据标记置零内部元素 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][0] == 0 || matrix[0][j] == 0) {  matrix[i][j] = 0; } } } // 处理第一列 if (firstColZero) { for (int i = 0; i < m; i++) { matrix[i][0] = 0; } } // 处理第一行 if (firstRowZero) { for (int j = 0; j < n; j++) { matrix[0][j] = 0; } } }}

Python

# 方法2: 原地标记法class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: \"\"\" Do not return anything, modify matrix in-place instead. \"\"\" m, n = len(matrix), len(matrix[0]) first_row_zero = any(matrix[0][j] == 0 for j in range(n)) first_col_zero = any(matrix[i][0] == 0 for i in range(m)) # 使用第一行和第一列作为标记 for i in range(1, m): for j in range(1, n): if matrix[i][j] == 0:  matrix[i][0] = matrix[0][j] = 0 # 根据标记置零内部元素 for i in range(1, m): for j in range(1, n): if matrix[i][0] == 0 or matrix[0][j] == 0:  matrix[i][j] = 0 # 处理第一行和第一列 if first_row_zero: matrix[0] = [0] * n if first_col_zero: for i in range(m): matrix[i][0] = 0

4、复杂度分析

方法 时间复杂度 空间复杂度 标记数组法 O(mn) O(m+n) 原地标记法 O(mn) O(1)

Q19、螺旋矩阵

1、题目描述

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

示例 1：

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

示例 2：

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

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

2、解题思路

1. 定义边界：初始化上、下、左、右四个边界
2. 顺时针遍历 ：
   • 从左到右遍历上边界
   • 从上到下遍历右边界
   • 从右到左遍历下边界（如果上边界不等于下边界）
   • 从下到上遍历左边界（如果左边界不等于右边界）
3. 收缩边界：每完成一个方向的遍历，就收缩对应的边界
4. 终止条件：当边界交叉时停止循环

3、代码实现

C++

class Solution {public: vector spiralOrder(vector<vector>& matrix) { vector ret; if (matrix.empty()) { return ret; } // 初始化四个边界 int upper = 0;  // 上边界 int down = matrix.size() - 1; // 下边界 int left = 0;  // 左边界 int right = matrix[0].size() - 1; // 右边界 while (true) { // 1. 从左到右遍历上边界 for (int i = left; i  down) { break; } // 2. 从上到下遍历右边界 for (int i = upper; i <= down; ++i) { ret.push_back(matrix[i][right]); } // 右边界左移, 并检查是否越界 if (--right = left; --i) { ret.push_back(matrix[down][i]); } // 下边界上移, 并检查是否越界 if (--down = upper; --i) { ret.push_back(matrix[i][left]); } // 左边界右移, 并检查是否越界 if (++left > right) { break; } } return ret; }};

Java

class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> ret = new ArrayList<>(); if (matrix == null || matrix.length == 0) { return ret; } int upper = 0; int down = matrix.length - 1; int left = 0; int right = matrix[0].length - 1; while (true) { // 从左到右 for (int i = left; i <= right; i++) { ret.add(matrix[upper][i]); } if (++upper > down) break; // 从上到下 for (int i = upper; i <= down; i++) { ret.add(matrix[i][right]); } if (--right < left) break; // 从右到左 for (int i = right; i >= left; i--) { ret.add(matrix[down][i]); } if (--down < upper) break; // 从下到上 for (int i = down; i >= upper; i--) { ret.add(matrix[i][left]); } if (++left > right) break; } return ret; }}

Python

class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: if not matrix: return [] ret = [] upper, down = 0, len(matrix) - 1 left, right = 0, len(matrix[0]) - 1 while True: # 从左到右 for i in range(left, right + 1): ret.append(matrix[upper][i]) upper += 1 if upper > down: break # 从上到下 for i in range(upper, down + 1): ret.append(matrix[i][right]) right -= 1 if right < left: break # 从右到左 for i in range(right, left - 1, -1): ret.append(matrix[down][i]) down -= 1 if down < upper: break # 从下到上 for i in range(down, upper - 1, -1): ret.append(matrix[i][left]) left += 1 if left > right: break return ret

4、复杂度分析

• 时间复杂度：O(mn)，需要访问矩阵中的每个元素一次
• 空间复杂度：O(1)，除了输出数组外只使用了常数空间

Q20、旋转图像

1、题目描述

给定一个 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]]

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

2、解题思路

方法一：直接旋转法

1. 分层处理：将矩阵看作由外到内的一层层正方形组成
2. 四元素交换：对于每个元素，找到旋转后对应的四个位置进行交换
3. 边界处理：对于奇数边长的矩阵，中心元素不需要旋转

方法二：翻转法

1. 水平翻转：先对矩阵进行水平翻转（上下翻转）
2. 主对角线翻转：然后沿主对角线进行翻转（转置）
3. 效果等同：这两步操作的结果等同于顺时针旋转90度

3、代码实现

C++

// 方法1: 直接旋转法class Solution {public: void rotate(vector<vector>& matrix) { int n = matrix.size(); // 分层处理, 从外层到内层 for (int i = 0; i < n / 2; ++i) { // 每层中需要旋转的元素数量 for (int j = 0; j < (n + 1) / 2; ++j) { int temp = matrix[i][j]; matrix[i][j] = matrix[n - j - 1][i]; matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]; matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]; matrix[j][n - i - 1] = temp; } } }};

// 方法2: 翻转法class Solution {public: void rotate(vector<vector>& matrix) { int n = matrix.size(); // 第一步: 水平翻转 (上下翻转) for (int i = 0; i < n / 2; ++i) { for (int j = 0; j < n; ++j) { swap(matrix[i][j], matrix[n - i - 1][j]); } } // 第二步: 主对角线翻转 (转置) for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { swap(matrix[i][j], matrix[j][i]); } } }};

Java

// 方法2: 翻转法class Solution { public void rotate(int[][] matrix) { int n = matrix.length; // 水平翻转 for (int i = 0; i < n / 2; i++) { for (int j = 0; j < n; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[n - i - 1][j]; matrix[n - i - 1][j] = temp; } } // 主对角线翻转 for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } }}

Python

# 方法2: 翻转法class Solution: def rotate(self, matrix: List[List[int]]) -> None: \"\"\" Do not return anything, modify matrix in-place instead. \"\"\" n = len(matrix) # 水平翻转 for i in range(n // 2): for j in range(n): matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j] # 主对角线翻转 for i in range(n): for j in range(i): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

4、复杂度分析

方法 时间复杂度 空间复杂度 直接旋转法 O(n²) O(1) 翻转法 O(n²) O(1)

Q21、搜索二维矩阵 II

1、题目描述

编写一个高效的算法来搜索 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

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -109 <= matrix[i][j] <= 109
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -109 <= target <= 109

2、解题思路

方法：缩减搜索空间法（从右上角开始）

1. 选择起点：从矩阵的右上角（或左下角）开始搜索
2. 比较移动 ：
   • 如果当前元素小于目标值，排除当前行（向下移动）
   • 如果当前元素大于目标值，排除当前列（向左移动）
   • 如果相等则找到目标
3. 终止条件：当行或列索引超出矩阵边界时停止

3、代码实现

C++

class Solution {public: bool searchMatrix(vector<vector>& matrix, int target) { // 获取矩阵的行数和列数 int m = matrix.size(); if (m == 0) { return false; } int n = matrix[0].size(); // 从右上角开始搜索 int row = 0, col = n - 1; while (row = 0) { if (matrix[row][col] == target) { // 找到目标值 return true; } else if (matrix[row][col] < target) { // 当前元素小于目标值, 排除当前行 (向下移动) row++; } else { // 当前元素大于目标值, 排除当前列 (向左移动) col--; } } // 遍历完未找到目标值 return false; }};

Java

class Solution { public boolean searchMatrix(int[][] matrix, int target) { // 检查矩阵是否为空 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return false; } int m = matrix.length; int n = matrix[0].length; // 从右上角开始搜索 int row = 0, col = n - 1; while (row < m && col >= 0) { if (matrix[row][col] == target) { return true; } else if (matrix[row][col] < target) { // 当前元素小于目标值，向下移动 row++; } else { // 当前元素大于目标值，向左移动 col--; } } return false; }}

Python

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: # 检查矩阵是否为空 if not matrix or not matrix[0]: return False m, n = len(matrix), len(matrix[0]) # 从右上角开始搜索 row, col = 0, n - 1 while row < m and col >= 0: if matrix[row][col] == target: return True elif matrix[row][col] < target: # 当前元素小于目标值，向下移动 row += 1 else: # 当前元素大于目标值，向左移动 col -= 1 return False

4、复杂度分析

• 时间复杂度：O(m + n)，最坏情况下需要遍历一行和一列的所有元素
• 空间复杂度：O(1)，仅使用常数空间

7、链表

Q22、相交链表

1、题目描述

给你两个单链表的头节点 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 。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

**进阶：**你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

2、解题思路

方法一：双指针法（最优解）

1. 指针初始化：两个指针分别指向两个链表的头节点
2. 同步移动：两个指针同时向前移动
3. 链表切换：当指针到达链表末尾时，切换到另一个链表的头部继续移动
4. 相遇点：当两个指针相遇时即为相交节点（若不相交则最终都为 null）

方法二：哈希表法

1. 遍历链表A：将所有节点存入哈希集合
2. 遍历链表B：检查每个节点是否存在于集合中
3. 返回结果：第一个存在于集合中的节点即为相交节点

方法三：长度差法

1. 计算长度：分别计算两个链表的长度
2. 调整指针：让长链表的指针先移动长度差步
3. 同步移动：然后两个指针同步前进，比较节点是否相同

3、代码实现

C++

// 方法1: 双指针法 (最优解)/** * 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) { if (headA == nullptr || headB == nullptr) { return nullptr; } ListNode *curA = headA, *curB = headB; // 当两个指针不相遇时, 继续循环 while (curA != curB) { // 指针到达末尾时, 切换到零一个链表的头部 curA = curA == nullptr ? headB : curA->next; curB = curB == nullptr ? headA : curB->next; } // 返回相遇节点 (如果不相交则返回 nullptr) return curA; }};

// 方法2: 哈希表法class Solution {public: ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { unordered_set visited; ListNode* cur = headA; // 遍历链表 A, 将所有节点存入哈希集合 while (cur != nullptr) { visited.insert(cur); cur = cur->next; } cur = headB; // 遍历链表 B, 检查节点是否在集合中 while (cur != nullptr) { if (visited.count(cur)) { return cur; } cur = cur->next; } return nullptr; }};

// 方法3: 长度差法class Solution {public: ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { int lenA = 0, lenB = 0; ListNode *curA = headA, *curB = headB; // 计算链表 A 的长度 while (curA != nullptr) { lenA++; curA = curA->next; } // 计算链表 B 的长度 while (curB != nullptr) { lenB++; curB = curB->next; } // 重置指针 curA = headA; curB = headB; // 让长链表的指针先移动长度差步 if (lenA > lenB) { for (int i = 0; i next; } } else { for (int i = 0; i next; } } // 同步移动两个指针, 寻找相交节点 while (curA != nullptr && curB != nullptr) { if (curA == curB) { return curA; } curA = curA->next; curB = curB->next; } return nullptr; }};

Java

// 方法1: 双指针法 (最优解)public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode a = headA, b = headB; while (a != b) { a = a == null ? headB : a.next; b = b == null ? headA : b.next; } return a; }}

Python

# 方法1: 双指针法 (最优解)# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]: if not headA or not headB: return None a, b = headA, headB while a != b: a = a.next if a else headB b = b.next if b else headA return a

4、复杂度分析

方法 时间复杂度 空间复杂度 双指针法 O(m+n) O(1) 哈希表法 O(m+n) O(m)或O(n) 长度差法 O(m+n) O(1)

Q23、反转链表

1、题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

2、解题思路

方法一：迭代法

1. 初始化：新建一个空指针 newhead，当前指针 cur 指向头节点
2. 遍历链表 ：
   • 保存当前节点的下一个节点
   • 将当前节点的 next 指向 newhead
   • 移动 newhead 到当前节点
   • 移动 cur 到保存的下一个节点
3. 返回结果：最后 newhead 就是反转后的链表头

方法二：递归法

1. 基准情形：如果链表为空或只有一个节点，直接返回
2. 递归反转：递归调用反转剩余链表
3. 调整指针：将当前节点的下一个节点的 next 指向当前节点
4. 断开连接：将当前节点的 next 置空
5. 返回结果：返回新的头节点

3、代码实现

C++

// 方法1: 迭代法/** * 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* newhead = nullptr; // 新链表的头节点初始为空 ListNode* cur = head; // 当前节点初始为原链表头 while (cur != nullptr) { ListNode* next = cur->next; // 保存下一个节点 cur->next = newhead; // 当前节点指向新链表头 newhead = cur;  // 更新新链表头为当前节点 cur = next;  // 移动当前节点到下一个节点 } return newhead; // 返回反转后的链表头 }};

// 方法2: 递归法class Solution {public: ListNode* reverseList(ListNode* head) { // 基准情况: 空链表或单链表直接返回 if (head == nullptr || head->next == nullptr) { return head; } // 递归反转剩余链表 ListNode* newhead = reverseList(head->next); // 调整指针方向 head->next->next = head; // 下一个节点指向当前节点 head->next = nullptr; // 当前节点指向空 return newhead; // 返回新的头节点 }};

Java

// 方法1: 迭代法class Solution { public ListNode reverseList(ListNode head) { ListNode newhead = null; ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = newhead; newhead = cur; cur = next; } return newhead; }}

// 方法2: 递归法class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode newhead = reverseList(head.next); head.next.next = head; head.next = null; return newhead; }}

Python

# 方法1: 迭代法class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: newhead = None cur = head while cur: next_node = cur.next # 保存下一个节点 cur.next = newhead # 反转指针 newhead = cur # 更新新头节点 cur = next_node # 移动到下一个节点 return newhead

# 方法2: 递归法class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return head newhead = self.reverseList(head.next) head.next.next = head head.next = None return newhead

4、复杂度分析

方法 时间复杂度 空间复杂度 迭代法 O(n) O(1) 递归法 O(n) O(n)（递归栈空间）

Q24、回文链表

1、题目描述

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

示例 1：

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

示例 2：

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

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

**进阶：**你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

2、解题思路

方法一：快慢指针+反转链表（最优解）

1. 找到中点：使用快慢指针找到链表的中点
2. 反转后半部分：将链表的后半部分反转
3. 比较前后部分：比较前半部分和反转后的后半部分是否相同
4. 恢复链表：将链表恢复原状（可选）
5. 返回结果：根据比较结果返回 true 或 false

方法二：数组辅助法

1. 复制到数组：将链表中的值复制到数组中
2. 双指针比较：使用双指针从数组两端向中间比较
3. 返回结果：根据比较结果返回 true 或 false

方法三：递归法

1. 递归到链表末尾：使用递归到达链表末尾
2. 回溯比较：在回溯过程中与链表头部开始比较
3. 移动头指针：每次比较后移动头指针
4. 返回结果：根据比较结果返回 true 或 false

3、代码实现

C++

// 方法1: 快慢指针+反转链表 (最优解)class Solution {public: bool isPalindrome(ListNode* head) { if (head == nullptr) { return true; } // 找到前半部分链表的尾节点并反转后半部分链表 ListNode* firstHalfEnd = endOfFirstHalf(head); ListNode* secondHalfStart = reverseList(firstHalfEnd->next); // 判断是否回文 ListNode* cur1 = head; ListNode* cur2 = secondHalfStart; bool result = true; while (result && cur2 != nullptr) { if (cur1->val != cur2->val) { result = false; } cur1 = cur1->next; cur2 = cur2->next; } // 还原链表并返回结果 firstHalfEnd->next = reverseList(secondHalfStart); return result; }private: // 反转链表辅助函数 ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } // 找到前半部分链表的尾节点辅助函数 ListNode* endOfFirstHalf(ListNode* head) { ListNode* fast = head; ListNode* slow = head; while (fast->next != nullptr && fast->next->next != nullptr) { fast = fast->next->next; slow = slow->next; } return slow; }};

// 方法2: 数组辅助函数class Solution {public: bool isPalindrome(ListNode* head) { ListNode* cur = head; vector vals; // 将链表值复制到数组 while (cur != nullptr) { vals.emplace_back(cur->val); cur = cur->next; } // 双指针比较数组 int n = vals.size(); for (int i = 0, j = n - 1; i < j; ++i, --j) { if (vals[i] != vals[j]) { return false; } } return true; }};

// 方法3: 递归法class Solution {private: ListNode* frontPoint; // 前向指针public: bool isPalindrome(ListNode* head) { frontPoint = head; return recursivelyCheck(head); }private: // 递归检查辅助函数 bool recursivelyCheck(ListNode* cur) { if (cur != nullptr) { // 递归到链表末尾 if (!recursivelyCheck(cur->next)) { return false; } // 比较当前节点值与前端指针值 if (cur->val != frontPoint->val) { return false; } // 移动前端指针 frontPoint = frontPoint->next; } return true; }};

Java

// 方法1: 快慢指针+反转链表 (最优解)/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public boolean isPalindrome(ListNode head) { if (head == null) { return true; } ListNode firstHalfEnd = endOfFirstHalf(head); ListNode secondHalfStart = reverseList(firstHalfEnd.next); ListNode p1 = head; ListNode p2 = secondHalfStart; boolean result = true; while (result && p2 != null) { if (p1.val != p2.val) { result = false; } p1 = p1.next; p2 = p2.next; } firstHalfEnd.next = reverseList(secondHalfStart); return result; } private ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; } private ListNode endOfFirstHalf(ListNode head) { ListNode fast = head; ListNode slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } return slow; }}

Python

# 方法1: 快慢指针+反转链表 (最优解)# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool: if not head: return True first_half_end = self.end_of_first_half(head) second_half_start = self.reverse_list(first_half_end.next) result = True p1 = head p2 = second_half_start while result and p2: if p1.val != p2.val: result = False p1 = p1.next p2 = p2.next first_half_end.next = self.reverse_list(second_half_start) return result def end_of_first_half(self, head): fast = head slow = head while fast.next and fast.next.next: fast = fast.next.next slow = slow.next return slow def reverse_list(self, head): prev = None curr = head while curr: next_temp = curr.next curr.next = prev prev = curr curr = next_temp return prev

4、复杂度分析

方法 时间复杂度 空间复杂度 快慢指针+反转链表 O(n) O(1) 数组辅助法 O(n) O(n) 递归法 O(n) O(n)（递归栈空间）

Q25、环形链表

1、题目描述

给你一个链表的头节点 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解释：链表中没有环。

提示：

• 链表中节点的数目范围是 [0, 104]
• -105 <= Node.val <= 105
• pos 为 -1 或者链表中的一个 有效索引 。

**进阶：**你能用 O(1)（即，常量）内存解决此问题吗？

2、解题思路

方法一：快慢指针法（最优解）

1. 初始化指针：设置两个指针 slow 和 fast 都指向头节点
2. 移动指针 ：
   • slow 指针每次移动一步
   • fast 指针每次移动两步
3. 检测相遇：如果 fast 和 slow 指针相遇，说明存在环
4. 终止条件：如果 fast 或 fast->next 为 null，说明链表无环

方法二：哈希表法

1. 初始化哈希表：创建一个哈希集合存储访问过的节点
2. 遍历链表 ：
   • 检查当前节点是否已在哈希集合中
   • 如果在集合中，说明存在环
   • 否则将当前节点加入集合
3. 终止条件：遍历到链表末尾 (null) 表示无环

3、代码实现

C++

// 方法1: 快慢指针class Solution {public: bool hasCycle(ListNode* head) { // 初始化快慢指针 ListNode* slow = head; ListNode* fast = head; // 当 fast 和 fast->next 不为空时继续移动 while (fast != nullptr && fast->next != nullptr) { slow = slow->next; // 慢指针走一步 fast = fast->next->next; // 快指针走两步 // 如果快慢指针相遇, 说明有环 if (slow == fast) { return true; } } // 遍历结果未相遇, 说明无环 return false; }};

// 方法2: 哈希表法class Solution {public: bool hasCycle(ListNode* head) { unordered_set visited; // 存储访问过的节点 ListNode* cur = head; while (cur != nullptr) { // 如果当前节点已经访问过, 说明有环 if (visited.count(cur)) { return true; } // 记录当前节点并移动到下一个节点 visited.insert(cur); cur = cur->next; } // 遍历结束未发现重复节点, 说明无环 return false; }};

Java

// 方法1: 快慢指针public class Solution { public boolean hasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true; } } return false; }}

// 方法2: 哈希表法public class Solution { public boolean hasCycle(ListNode head) { Set<ListNode> visited = new HashSet<>(); ListNode current = head; while (current != null) { if (visited.contains(current)) { return true; } visited.add(current); current = current.next; } return false; }}

Python

# 方法1: 快慢指针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 slow == fast: return True return False

# 方法2: 哈希表法class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: visited = set() current = head while current: if current in visited: return True visited.add(current) current = current.next return False

4、复杂度分析

方法 时间复杂度 空间复杂度 快慢指针法 O(n) O(1) 哈希表法 O(n) O(n)

Q26、环形链表 II

1、题目描述

给定一个链表的头节点 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解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

**进阶：**你是否可以使用 O(1) 空间解决此题？

2、解题思路

方法一：快慢指针法（最优解）

1. 检测环存在：使用快慢指针检测是否有环
2. 寻找入口：当快慢指针相遇后，将一个指针重置到头部，然后两个指针以相同速度移动，再次相遇的节点就是环入口
3. 数学原理：设链表头到入口距离为a，入口到相遇点距离为b，相遇点到入口距离为c，有2(a+b)=a+b+n(b+c)，推导得a=c+(n-1)(b+c)

方法二：哈希表法

1. 记录访问节点：使用哈希集合记录访问过的节点
2. 检测重复：遍历链表，当遇到第一个重复访问的节点时，即为环的入口
3. 终止条件：遍历到链表末尾 (null) 表示无环

3、代码实现

C++

// 方法1: 快慢指针法/** * 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; bool hasCycle = false; // 第一步: 检测是否有环 while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if (slow == fast) { hasCycle = true; break; } } // 如果没有环, 直接返回 null if (!hasCycle) { return nullptr; } // 第二步: 找到环的入口 slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; }};

// 方法2: 哈希表法class Solution {public: ListNode* detectCycle(ListNode* head) { unordered_set visited; ListNode* current = head; while (current != nullptr) { // 如果节点已经访问过, 说明是环的入口 if (visited.count(current)) { return current; } // 记录访问过的节点 visited.insert(current); current = current->next; } // 遍历结束未发现环 return nullptr; }};

Java

// 方法1: 快慢指针法/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow = head, fast = head; boolean hasCycle = false; // 检测是否有环 while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { hasCycle = true; break; } } // 无环则返回null if (!hasCycle) { return null; } // 寻找环入口 slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; }}

// 方法2: 哈希表法public class Solution { public ListNode detectCycle(ListNode head) { Set<ListNode> visited = new HashSet<>(); ListNode current = head; while (current != null) { if (visited.contains(current)) { return current; } visited.add(current); current = current.next; } return null; }}

Python

# 方法1: 快慢指针法class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: # 检测是否有环 slow = fast = head has_cycle = False while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: has_cycle = True break if not has_cycle: return None # 寻找环入口 slow = head while slow != fast: slow = slow.next fast = fast.next  return slow

# 方法2: 哈希表法class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: visited = set() current = head while current: if current in visited: return current visited.add(current) current = current.next return None

4、复杂度分析

方法 时间复杂度 空间复杂度 快慢指针法 O(n) O(1) 哈希表法 O(n) O(n)

Q27、合并两个有序链表

1、题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

2、解题思路

方法一：迭代法

1. 创建哑节点：创建一个哑节点作为新链表的起始点
2. 比较并连接：同时遍历两个链表，比较当前节点的值，将较小的节点连接到新链表
3. 处理剩余节点：当其中一个链表遍历完后，将另一个链表的剩余部分直接连接到新链表末尾
4. 返回结果：返回哑节点的下一个节点作为合并后的链表头

方法二：递归法

1. 基准情况：如果其中一个链表为空，直接返回另一个链表
2. 比较节点：比较两个链表头节点的值
3. 递归合并：将较小节点的next指针指向递归合并的结果
4. 返回结果：返回较小的节点作为当前合并结果

3、代码实现

C++

// 方法1: 迭代class Solution {public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode dummy; // 创建哑节点作为新链表的起始点 ListNode* current = &dummy; // 当前节点指针 // 同时遍历两个链表 while (list1 != nullptr && list2 != nullptr) { // 比较两个链表当前节点的值 if (list1->val val) { current->next = list1; // 连接较小的节点 list1 = list1->next; // 连接链表 1 指针 } else { current->next = list2; // 连接较小的节点 list2 = list2->next; // 移动链表 2 指针 } current = current->next; // 移动当前指针 } // 处理剩余节点 current->next = (list1 != nullptr) ? list1 : list2; // 返回合并后的链表头 (哑节点的下一个节点) return dummy.next; }};

// 方法2: 递归class Solution {public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { // 基准情况: 如果一个链表为空, 返回另一个链表 if (list1 == nullptr) { return list2; } if (list2 == nullptr) { return list1; } // 比较两个链表头节点的值 if (list1->val val) { // 递归合并, 将较小节点的 next 指向合并结果 list1->next = mergeTwoLists(list1->next, list2); return list1; } else { list2->next = mergeTwoLists(list1, list2->next); return list2; } }};

Java

// 方法1: 迭代class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(); // 哑节点 ListNode current = dummy; // 当前指针 while (list1 != null && list2 != null) { if (list1.val < list2.val) { current.next = list1; list1 = list1.next; } else { current.next = list2; list2 = list2.next; } current = current.next; } // 连接剩余节点 current.next = (list1 != null) ? list1 : list2; return dummy.next; }}

// 方法2: 递归class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if (list1 == null) { return list2; } if (list2 == null) { return list1; } if (list1.val < list2.val) { list1.next = mergeTwoLists(list1.next, list2); return list1; } else { list2.next = mergeTwoLists(list1, list2.next); return list2; } }}

Python

# 方法1: 迭代class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() # 哑节点 current = dummy # 当前指针 while list1 and list2: if list1.val < list2.val: current.next = list1 list1 = list1.next else: current.next = list2 list2 = list2.next current = current.next # 连接剩余节点 current.next = list1 if list1 else list2 return dummy.next

# 方法2: 递归class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: if not list1: return list2 if not list2: return list1 if list1.val < list2.val: list1.next = self.mergeTwoLists(list1.next, list2) return list1 else: list2.next = self.mergeTwoLists(list1, list2.next) return list2

4、复杂度分析

方法 时间复杂度 空间复杂度 迭代法 O(n+m) O(1) 递归法 O(n+m) O(n+m)（递归栈空间）

Q28、两数相加

1、题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 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]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

2、解题思路

1. 初始化：创建一个哑节点作为结果链表的起始点，设置进位为0
2. 遍历链表：同时遍历两个链表，直到两个链表都遍历完且没有进位
3. 计算和：将当前位的两个数字相加，加上进位
4. 处理进位：计算当前位的值（和%10）和新的进位（和/10）
5. 创建新节点：将当前位的值存入新节点
6. 处理剩余节点：当一个链表遍历完后，继续处理另一个链表和可能的进位
7. 返回结果：返回哑节点的下一个节点作为结果链表的头

3、代码实现

C++

class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode dummy; // 创建哑节点作为结果链表的起始点 ListNode* current = &dummy; // 当前结点指针 int carry = 0;  // 进位初始化为 0 // 遍历两个链表, 直到都遍历完且没有进位 while (l1 != nullptr || l2 != nullptr || carry != 0) { int sum = carry; // 当前位的和初始化为进位制 // 如果 l1 还有节点, 加上其值并移动到下一个节点 if (l1 != nullptr) { sum += l1->val; l1 = l1->next; } // 如果 l2 还有节点, 加上其值并移动到下一个节点 if (l2 != nullptr) { sum += l2->val; l2 = l2->next; } // 计算当前位的值和新的进位 carry = sum / 10; current->next = new ListNode(sum % 10); // 创建新节点存储当前位的值 current = current->next; // 移动当前指针 } return dummy.next; // 返回结果链表的头节点 }};

Java

class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(); // 哑节点 ListNode current = dummy; // 当前指针 int carry = 0; // 进位 while (l1 != null || l2 != null || carry != 0) { int sum = carry; if (l1 != null) { sum += l1.val; l1 = l1.next; } if (l2 != null) { sum += l2.val; l2 = l2.next; } carry = sum / 10; current.next = new ListNode(sum % 10); current = current.next; } return dummy.next; }}

Python

class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() # 哑节点 current = dummy # 当前指针 carry = 0  # 进位 while l1 or l2 or carry: sum_val = carry if l1: sum_val += l1.val l1 = l1.next if l2: sum_val += l2.val l2 = l2.next carry = sum_val // 10 current.next = ListNode(sum_val % 10) current = current.next  return dummy.next

4、复杂度分析

• 时间复杂度：O(max(n,m))，其中n和m分别是两个链表的长度
• 空间复杂度：O(max(n,m))，结果链表的长度最多为max(n,m)+1

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

1、题目描述

给你一个链表，删除链表的倒数第 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]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

**进阶：**你能尝试使用一趟扫描实现吗？

2、解题思路

方法一：两次遍历法

1. 计算链表长度：第一次遍历统计链表长度
2. 定位删除位置：第二次遍历找到倒数第n个节点的前驱节点
3. 执行删除操作：修改前驱节点的next指针，跳过待删除节点

方法二：栈方法

1. 节点入栈：将所有节点压入栈中
2. 弹出n个节点：弹出栈顶的n个节点
3. 定位前驱节点：此时栈顶节点即为倒数第n个节点的前驱
4. 执行删除操作：修改前驱节点的next指针

方法三：快慢指针法（最优解）

1. 初始化指针：创建哑节点，并初始化快慢指针指向它
2. 移动快指针：先将快指针移动n步
3. 同步移动：然后同时移动快慢指针，直到快指针到达末尾
4. 执行删除：此时慢指针指向倒数第n个节点的前驱，执行删除操作

3、代码实现

C++

// 方法1: 两次遍历法class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(0, head); // 创建哑节点 ListNode* current = head; int length = 0; // 第一次遍历: 计算链表长度 while (current != nullptr) { current = current->next; length++; } // 第二次遍历: 找到倒数第 n 个节点的前驱 current = dummy; for (int i = 0; i next; } // 删除节点 ListNode* toDelete = current->next; current->next = toDelete->next; delete toDelete; ListNode* result = dummy->next; delete dummy; return result; }};

// 方法2: 栈方法class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(0, head); // 创建哑节点 stack stk; ListNode* current = dummy; // 将所有节点压入栈 while (current != nullptr) { stk.push(current); current = current->next; } // 弹出 n 个节点 for (int i = 0; i next; prev->next = toDelete->next; delete toDelete; ListNode* result = dummy->next; delete dummy; return result; }};

// 方法3: 快慢指针法class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0); // 创建哑节点 dummy.next = head; ListNode* fast = &dummy; ListNode* slow = &dummy; // 快指针先走 n 步 for (int i = 0; i next; } // 快慢指针同时移动, 直到快指针到达末尾 while (fast->next != nullptr) { fast = fast->next; slow = slow->next; } // 此时慢指针指向倒数第 n 个节点的前驱 ListNode* toDelete = slow->next; slow->next = toDelete->next; delete toDelete; return dummy.next; }};

Java

// 方法3: 快慢指针法class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); // 哑节点 dummy.next = head; ListNode fast = dummy; ListNode slow = dummy; // 快指针先走n步 for (int i = 0; i < n; i++) { fast = fast.next; } // 快慢指针同时移动 while (fast.next != null) { fast = fast.next; slow = slow.next; } // 删除节点 slow.next = slow.next.next; return dummy.next; }}

Python

# 方法3: 快慢指针法class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy = ListNode(0) # 哑节点 dummy.next = head fast = slow = dummy # 快指针先走n步 for _ in range(n): fast = fast.next # 快慢指针同时移动 while fast.next: fast = fast.next slow = slow.next # 删除节点 slow.next = slow.next.next return dummy.next

4、复杂度分析

方法 时间复杂度 空间复杂度 两次遍历法 O(n) O(1) 栈方法 O(n) O(n) 快慢指针法 O(n) O(1)

Q30、两两交换链表中的节点

1、题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

2、解题思路

方法一：递归法

1. 基准情况：链表为空或只有一个节点时直接返回
2. 交换节点：将第一个节点指向递归处理剩余部分的结果
3. 连接新头：将第二个节点指向第一个节点
4. 返回新头：返回新的头节点（原第二个节点）

方法二：迭代法（哑节点）

1. 创建哑节点：简化头节点处理
2. 初始化指针：设置当前指针指向哑节点
3. 交换过程 ：
   • 记录要交换的两个节点
   • 调整指针关系完成交换
   • 移动当前指针到下一组的前驱位置
4. 返回结果：返回哑节点的next

方法三：迭代法（三指针）

1. 创建哑节点：简化头节点处理
2. 初始化指针：设置前驱、当前和下一个节点指针
3. 交换过程 ：
   • 调整三个指针的关系完成交换
   • 移动指针到下一组的前驱位置
4. 返回结果：返回哑节点的next

3、代码实现

C++

// 方法1: 递归法class Solution {public: ListNode* swapPairs(ListNode* head) { // 基准情况: 空链表或单链表 if (head == nullptr || head->next == nullptr) { return head; } // 新的头节点是原第二个节点 ListNode* newHead = head->next; // 原第一个节点指向递归处理剩余部分的结果 head->next = swapPairs(newHead->next); // 新头节点指向原第一个节点 newHead->next = head; return newHead; }};

// 方法2: 迭代法 (哑节点)class Solution {public: ListNode* swapPairs(ListNode* head) { ListNode dummy; // 创建哑节点 dummy.next = head; ListNode* current = &dummy; // 当前指针指向哑节点 // 当存在至少两个节点可交换时 while (current->next && current->next->next) { // 记录要交换的两个节点 ListNode* node1 = current->next; ListNode* node2 = current->next->next; // 执行交换操作 current->next = node2; // 前驱指向第二个节点 node1->next = node2->next; // 第一个节点指向后续节点 node2->next = node1; // 移动当前指针到下一组的前驱位置 current = node1; } return dummy.next; }};

// 方法3: 迭代法 (三指针)/** * 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) { // 处理边界情况 if (head == nullptr || head->next == nullptr) { return head; } ListNode dummy; // 创建哑节点 dummy.next = head; ListNode* prev = &dummy; // 前驱指针 ListNode* curr = head; // 当前指针 ListNode* next = curr->next; // 下一个指针 while (curr && next) { // 执行交换 prev->next = next; curr->next = next->next; next->next = curr; // 移动指针到下一组的前驱位置 prev = curr; curr = curr->next; if (curr) { next = curr->next; } } return dummy.next; }};

Java

// 方法2: 迭代法 (哑节点)class Solution { public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(0); // 哑节点 dummy.next = head; ListNode current = dummy; while (current.next != null && current.next.next != null) { ListNode first = current.next; ListNode second = current.next.next; // 执行交换 current.next = second; first.next = second.next; second.next = first; // 移动指针 current = first; } return dummy.next; }}

Python

// 方法2: 迭代法 (哑节点)class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode(0) # 哑节点 dummy.next = head current = dummy while current.next and current.next.next: # 记录要交换的节点 first = current.next second = current.next.next # 执行交换 current.next = second first.next = second.next second.next = first # 移动指针 current = first return dummy.next

4、复杂度分析

方法 时间复杂度 空间复杂度 递归法 O(n) O(n)（递归栈空间） 迭代法（哑节点） O(n) O(1) 迭代法（三指针） O(n) O(1)

Q31、K 个一组翻转链表

1、题目描述

给你链表的头节点 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]

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

**进阶：**你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

2、解题思路

1. 计算翻转组数：先遍历链表计算总长度，然后除以k得到需要翻转的组数
2. 分组翻转 ：
   • 使用头插法对每组k个节点进行翻转
   • 维护前驱节点prev，指向当前组的虚拟头节点
   • 每组翻转后，prev移动到该组翻转后的最后一个节点
3. 连接剩余节点：将翻转后的链表与剩余不足k个的节点连接起来

3、代码实现

C++

class Solution {public: ListNode* reverseKGroup(ListNode* head, int k) { // 1. 计算链表长度和需要翻转的数组 int length = 0; ListNode* cur = head; while (cur) { length++; cur = cur->next; } int group = length / k; // 计算完整翻转的数组 // 2. 创建虚拟头节点简化操作 ListNode dummy(0); ListNode* prev = &dummy; cur = head; // 3. 对每组进行翻转 for (int i = 0; i < group; ++i) { ListNode* groupTail = cur; // 记录当前组的原始头节点, 翻转后头节点变成尾节点 // 使用头插法翻转当前组 for (int j = 0; j next; // 保存下一个节点 cur->next = prev->next; // 当前节点指向 prev 的下一个节点 prev->next = cur;  // prev 指向当前节点 cur = next;  // 移动到下一个节点 } prev = groupTail; } // 4. 连接剩余不足 k 个的节点 prev->next = cur; return dummy.next; }};

Java

class Solution { public ListNode reverseKGroup(ListNode head, int k) { // 1. 计算链表长度 int length = 0; ListNode curr = head; while (curr != null) { length++; curr = curr.next; } int groups = length / k; // 计算完整翻转的组数 // 2. 创建虚拟头节点 ListNode dummy = new ListNode(0); ListNode prev = dummy; curr = head; // 3. 分组翻转 for (int i = 0; i < groups; i++) { ListNode groupTail = curr; // 记录当前组的原始头节点 // 使用头插法翻转当前组 for (int j = 0; j < k; j++) { ListNode next = curr.next; curr.next = prev.next; prev.next = curr; curr = next; } prev = groupTail; // 更新prev为当前组的尾节点 } // 4. 连接剩余节点 prev.next = curr; return dummy.next; }}

Python

class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: # 1. 计算链表长度 length = 0 curr = head while curr: length += 1 curr = curr.next groups = length // k # 计算完整翻转的组数 # 2. 创建虚拟头节点 dummy = ListNode(0) prev = dummy curr = head # 3. 分组翻转 for _ in range(groups): group_tail = curr # 记录当前组的原始头节点 # 使用头插法翻转当前组 for _ in range(k): next_node = curr.next curr.next = prev.next prev.next = curr curr = next_node prev = group_tail # 更新prev为当前组的尾节点 # 4. 连接剩余节点 prev.next = curr return dummy.next

4、复杂度分析

• 时间复杂度：O(n)，需要遍历链表两次（一次计算长度，一次执行翻转）
• 空间复杂度：O(1)，只使用了常数个额外指针

Q32、随机链表的复制

1、题目描述

给你一个长度为 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]]

提示：

• 0 <= n <= 1000
• -104 <= Node.val <= 104
• Node.random 为 null 或指向链表中的节点。

2、解题思路

方法一：节点拆分法（最优解）

1. 复制节点：在原链表的每个节点后面插入一个复制节点
2. 设置随机指针：根据原节点的 random 指针设置复制节点的 random 指针
3. 分离链表：将复制链表从原链表中分离出来

方法二：哈希表递归法

1. 哈希表映射：使用哈希表存储原节点到新节点的映射
2. 递归创建：递归创建 next 和 random 指针指向的节点

方法三：哈希表迭代法

1. 哈希表映射：使用哈希表存储原节点到新节点的映射
2. 两次遍历：第一次创建所有节点，第二次设置指针关系

3、代码实现

C++

// 方法1: 节点拆分法class Solution {public: Node* copyRandomList(Node* head) { if (!head) { return nullptr; } // 1. 复制每个节点并插入到原节点后面 Node* curr = head; while (curr) { Node* newNode = new Node(curr->val); newNode->next = curr->next; curr->next = newNode; curr = newNode->next; } // 2. 设置复制节点的 random 指针 curr = head; while (curr) { if (curr->random) { curr->next->random = curr->random->next; } curr = curr->next->next; } // 3. 分离链表 Node* newHead = head->next; curr = head; while (curr) { Node* tmp = curr->next; curr->next = tmp->next; if (tmp->next) { tmp->next = tmp->next->next; } curr = curr->next; } return newHead; }};

// 方法2: 哈希表递归class Solution {private: unordered_map visited;public: Node* copyRandomList(Node* head) { if (!head) { return nullptr; } // 如果已经创建过该节点的拷贝, 直接返回 if (visited.find(head) != visited.end()) { return visited[head]; } // 创建新结点 Node* newNode = new Node(head->val); visited[head] = newNode; // 递归设置 next 和 random 指针 newNode->next = copyRandomList(head->next); newNode->random = copyRandomList(head->random); return newNode; }};

// 方法3: 迭代+节点拆分class Solution {public: Node* copyRandomList(Node* head) { if (head == nullptr) { return nullptr; } for (Node* node = head; node != nullptr; node = node->next->next) { Node* newnode = new Node(node->val); newnode->next = node->next; node->next = newnode; } for (Node* node = head; node != nullptr; node = node->next->next) { Node* newnode = node->next; newnode->random = (node->random != nullptr) ? node->random->next : nullptr; } Node* newhead = head->next; for (Node* node = head; node != nullptr; node = node->next) { Node* newnode = node->next; node->next = node->next->next; newnode->next = (newnode->next != nullptr) ? newnode->next->next : nullptr; } return newhead; }};

Java

class Solution { public Node copyRandomList(Node head) { if (head == null) { return null; } // 1. 复制每个节点并插入到原节点后面 Node curr = head; while (curr != null) { Node newNode = new Node(curr.val); newNode.next = curr.next; curr.next = newNode; curr = newNode.next; } // 2. 设置复制节点的random指针 curr = head; while (curr != null) { if (curr.random != null) { curr.next.random = curr.random.next; } curr = curr.next.next; } // 3. 分离链表 Node newHead = head.next; curr = head; while (curr != null) { Node temp = curr.next; curr.next = temp.next; if (temp.next != null) { temp.next = temp.next.next; } curr = curr.next; } return newHead; }}

Python

class Solution: def copyRandomList(self, head: \'Optional[Node]\') -> \'Optional[Node]\': if not head: return None # 1. 复制每个节点并插入到原节点后面 curr = head while curr: new_node = Node(curr.val) new_node.next = curr.next curr.next = new_node curr = new_node.next # 2. 设置复制节点的random指针 curr = head while curr: if curr.random: curr.next.random = curr.random.next curr = curr.next.next # 3. 分离链表 new_head = head.next curr = head while curr: temp = curr.next curr.next = temp.next if temp.next: temp.next = temp.next.next curr = curr.next return new_head

4、复杂度分析

方法 时间复杂度 空间复杂度 节点拆分法 O(n) O(1) 哈希表递归法 O(n) O(n) 哈希表迭代法 O(n) O(n)

Q33、排序链表

1、题目描述

给你链表的头结点 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 = []输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 104] 内
• -105 <= Node.val <= 105

**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

2、解题思路

方法一：归并排序（递归版）

1. 找到中点：使用快慢指针找到链表的中点
2. 递归排序：分别对前半部分和后半部分递归排序
3. 合并有序链表：将两个已排序的子链表合并

方法二：归并排序（迭代版）

1. 自底向上归并：从最小的子链表(长度为1)开始归并
2. 逐步扩大归并规模：每次将归并的子链表长度翻倍
3. 合并有序链表：将两个已排序的子链表合并

3、代码实现

C++

// 方法1: 递归归并排序class Solution {public: ListNode* sortList(ListNode* head) { // 递归终止条件 if (head == nullptr || head->next == nullptr) { return head; } // 使用快慢指针找到中点 ListNode *slow = head, *fast = head->next; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; } // 分割链表 ListNode* mid = slow->next; slow->next = nullptr; // 递归排序两个子链表 ListNode* left = sortList(head); ListNode* right = sortList(mid); // 合并有序链表 return merge(left, right); }private: ListNode* merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur = &dummy; while (l1 && l2) { if (l1->val val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } cur->next = l1 ? l1 : l2; return dummy.next; }};

// 方法2: 迭代归并排序class Solution {public: ListNode* sortList(ListNode* head) { if (!head || !head->next) { return head; } // 计算链表长度 int len = 0; ListNode* cur = head; while (cur) { len++; cur = cur->next; } ListNode* dummy(0); dummy.next = head; // 从 1 开始, 每次翻倍 for (int step = 1; step < len; step <<= 1) { ListNode* prev = &dummy; cur = dummy.next; while (cur) { // 获取第一个子链表 ListNode* left = cur; for (int i = 1; i next; ++i) {  cur = cur->next; } // 获取第二个子链表 ListNode* right = cur->next; cur->next = nullptr; // 断开第一个子链表 cur = right; for (int i = 1; i next; ++i) {  cur = cur->next; } // 保存下一组的起点 ListNode* next = nullptr; if (cur) {  next = cur->next;  cur->next = nullptr; // 断开第二个子链表 } // 合并两个子链表 prev->next = merge(left, right); // 移动 prev 到已排序部分的末尾 while (prev->next) {  prev = prev->next; } cur = next; // 处理下一组 } } return dummy.next; }private: ListNode* merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur = &dummy; while (l1 && l2) { if (l1->val val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } cur->next = l1 ? l1 : l2; return dummy.next; }};

Java

// 方法1: 递归归并排序class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } // 找到中点 ListNode slow = head, fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // 分割链表 ListNode mid = slow.next; slow.next = null; // 递归排序 ListNode left = sortList(head); ListNode right = sortList(mid); // 合并 return merge(left, right); } private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode cur = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = l1 != null ? l1 : l2; return dummy.next; }}

Python

# 方法1: 递归归并排序class Solution: def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return head # 找到中点 slow, fast = head, head.next while fast and fast.next: slow = slow.next fast = fast.next.next # 分割链表 mid = slow.next slow.next = None # 递归排序 left = self.sortList(head) right = self.sortList(mid) # 合并 return self.merge(left, right) def merge(self, l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode(0) cur = dummy while l1 and l2: if l1.val < l2.val: cur.next = l1 l1 = l1.next else: cur.next = l2 l2 = l2.next cur = cur.next cur.next = l1 if l1 else l2 return dummy.next

4、复杂度分析

方法 时间复杂度 空间复杂度 递归归并 O(n log n) O(log n)（递归栈空间） 迭代归并 O(n log n) O(1)