在攻克了 数组原地修改 (同向快慢指针) 之后，双指针算法还有两块重要的拼图：“左右指针”（相向而行）和 “中心扩散”（背向而行）。

这两类技巧常用于解决字符串反转、有序数组搜索以及回文串查找等问题，是字节跳动等大厂面试中极高频的考点。

LeetCode 83. 删除排序链表中的重复元素（Easy）

题目链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-list/

标签：链表 | 双指针 | 原地修改

所属模块：链表与双指针

最后复习日期：2026-02-01

复习次数：1

掌握程度：🌟🌟🌟（初次整理）

1. 题目描述

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

  • 输入：head = [1,1,2,3,3]
  • 输出：[1,2,3]
  • 约束条件：链表长度范围 [0, 300]，题目数据保证链表已经按升序排列。

2. 核心框架 / 套路归纳

  • 这题本质是 同向快慢指针（Fast-Slow Pointers） 问题，是数组去重逻辑在链表上的映射。

  • 适用框架：

    1
    2
    3
    4
    5
    6
    7
    8
    // 链表双指针基础模型
    while (fast != null) {
        if (需保留) {
            slow.next = fast;
            slow = slow.next;
        }
        fast = fast.next;
    }

  • 为什么用这个框架？ 链表有序，重复元素必然相邻。通过快指针探路、慢指针维护“不重复区域”的尾部，可以 $O(N)$ 一次遍历完成去重。

3. 思路分析

  1. 逻辑映射
    • 数组去重（LC 26）：nums[slow] = nums[fast]（搬运数值）。
    • 链表去重（LC 83）：slow.next = fast（搬运指针，改变引用指向）。
  2. 核心步骤
    • 初始化 slow 和 fast 指向头节点。
    • fast 向后遍历：
      • 如果 slow.val == fast.val：说明是重复项，fast 继续走，忽略它。
      • 如果 slow.val != fast.val：说明是新元素，将 slow.next 指向 fast，并将 slow 前进到 fast 的位置。
    • 关键收尾：循环结束后，必须执行 slow.next = null，断开链表后面可能残留的重复节点（例如 1->2->3->3，不切断最后会变成 1->2->3->3 而不是 1->2->3）。

4. 代码实现

Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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 ListNode deleteDuplicates(ListNode head) {
        // 1. 边界检查
        if (head == null) {
            return null;
        }
        
        ListNode slow = head, fast = head;    
        while (fast != null) {
            if (slow.val == fast.val) {
                // 遇到重复，快指针只管继续往后找
                fast = fast.next;
            } else {
                // 遇到新值，将慢指针的 next 指向快指针
                slow.next = fast;
                // 更新慢指针位置
                slow = fast;
            }        
        }
        // 2. 关键：断开后面可能存在的重复元素连接，防止链表尾部残留
        slow.next = null;
        return head;
    }
}

5. 复杂度分析

  • 时间复杂度：$O(N)$

    理由：fast 指针遍历链表一次。

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

    理由：只使用了 slow 和 fast 两个引用变量，未开辟额外空间。

6. 易错点 & 调试经验

  • 断尾操作：最容易遗忘 slow.next = null。如果链表尾部是重复元素（如 ...->3->3），不打断连接会导致死循环或输出错误。
  • 空指针防御：输入 head 为空时，直接访问 head.val 会报错。
  • 引用操作：链表操作是修改 next 指针，而不是像数组那样赋值 val（虽然这题也可以改 val，但不仅不通用，面试也会被认为是投机取巧）。

7. 相关变式 & 高频延伸题目

8. 个人心得 & 复习建议

  • 一句话总结：链表去重就是“快指针探路，慢指针筑墙”，别忘了最后手动封墙（断尾）。
  • 下次复习重点：对比 LC 82，理解为什么 82 需要 dummy node 而 83 不需要。
  • 快速回顾卡片：
    • 框架：快慢指针。
    • 易错点：slow.next = null。
    • 复杂度：$O(N)$ / $O(1)$。

LeetCode 344. 反转字符串（Easy）

题目链接：https://leetcode.cn/problems/reverse-string/

标签：字符串 | 双指针 | 左右指针

所属模块：数组与字符串

最后复习日期：2026-02-01

复习次数：1

掌握程度：🌟🌟🌟

1. 题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

必须原地修改输入数组、使用 $O(1)$ 的额外空间解决这一问题。

  • 输入：s = ["h","e","l","l","o"]
  • 输出：["o","l","l","e","h"]

2. 核心框架 / 套路归纳

  • 这题本质是 左右指针（Left-Right Pointers） 问题。

  • 适用框架：

    1
    2
    3
    4
    5
    int left = 0, right = s.length - 1;
    while (left < right) {
        swap(s, left, right);
        left++; right--;
    }

  • 为什么用这个框架？ 字符串反转具有中心对称性，从两端向中间逼近交换是最直观且空间最优的解法。

3. 思路分析

  1. 暴力思路
    • 开辟一个新的数组，倒序遍历原数组填入。
    • 缺陷：空间复杂度 $O(N)$，不符合题目“原地修改”的要求。
  2. 优化思路（双指针）
    • 定义 left 指向头部，right 指向尾部。
    • 每次交换 s[left] 和 s[right]。
    • left 向右移，right 向左移，直到两者相遇（left >= right）。

4. 代码实现

Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void reverseString(char[] s) {
        // 1. 防御性编程
        if (s == null || s.length == 0) {
            return;
        }
        
        // 2. 初始化左右指针
        int left = 0, right = s.length - 1;
        
        // 3. 向中间逼近，交换元素
        while (left < right) {
            char tmp = s[right];
            s[right] = s[left];
            s[left] = tmp;
            
            // 指针移动
            left++;
            right--;
        }
    }
}

5. 复杂度分析

  • 时间复杂度：$O(N)$

    理由：两个指针一共遍历了整个数组一次（各走一半）。

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

    理由：只使用了一个临时变量 tmp。

6. 易错点 & 调试经验

  • 循环条件：left < right 即可，写 left <= right 也没错，但中间那个元素自己交换自己没必要。
  • API 限制：面试官通常禁止使用 StringBuilder.reverse() 或 Python 的 s[::-1]，因为考察的是算法思维。

7. 相关变式 & 高频延伸题目

8. 个人心得 & 复习建议

  • 一句话总结：左右指针最基础的用法，是所有“反转类”题目的基石。
  • 快速回顾卡片：
    • 框架：left, right 向中间挤。
    • 关键：tmp 变量交换。

LeetCode 167. 两数之和 II - 输入有序数组（Medium）

题目链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/

标签：数组 | 左右指针 | 二分查找

所属模块：数组与双指针

最后复习日期：2026-02-01

复习次数：1

掌握程度：🌟🌟🌟

1. 题目描述

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。

  • 输入：numbers = [2,7,11,15], target = 9
  • 输出：[1,2]
  • 约束条件：numbers 是有序的，且假设只有唯一解。

2. 核心框架 / 套路归纳

  • 这题本质是 左右指针（相向搜索） 问题。

  • 适用框架：

    1
    2
    3
    4
    5
    6
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return ...;
        else if (sum < target) left++;
        else right--;
    }

  • 为什么用这个框架？ 数组有序是核心暗示。利用单调性，sum 大了就减小大数（右指针左移），sum 小了就增大小数（左指针右移），可以将搜索空间从二维矩阵对角线压缩到一维。

3. 思路分析

  1. 暴力思路
    • 双层循环遍历所有组合。
    • 时间复杂度 $O(N^2)$，超时。
  2. 哈希表思路（LC 1. 两数之和）
    • 用 HashMap 存已访问过的数字。
    • 时间 $O(N)$，空间 $O(N)$。虽然可行，但没有利用“有序”这个强条件，空间不是最优。
  3. 双指针优化思路
    • 初始化 left=0, right=n-1。
    • 计算 sum = numbers[left] + numbers[right]。
    • 决策：
      • 若 sum > target：说明 numbers[right] 太大，必须变小，所以 right--。
      • 若 sum < target：说明 numbers[left] 太小，必须变大，所以 left++。
      • 若 sum == target：找到答案。

4. 代码实现

Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // 1. 边界防御
        if (numbers == null || numbers.length == 0) {
            return new int[]{-1, -1};
        }
        
        // 2. 初始化左右指针
        int left = 0, right = numbers.length - 1;
        
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            
            if (sum == target) {
                // 3. 匹配成功：返回 1-based 索引
                // 注意题目要求从 1 开始，所以用 left + 1
                return new int[]{left + 1, right + 1};
            } else if (sum > target) {
                // 和太大 -> 让右边的（大数）变小一点
                right--;
            } else {
                // 和太小 -> 让左边的（小数）变大一点
                left++;
            }   
        }
        
        // 4. 兜底返回
        return new int[]{-1, -1};
    }
}

5. 复杂度分析

  • 时间复杂度：$O(N)$

    理由：最坏情况下，左右指针共同遍历整个数组一次。

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

    理由：仅使用了常数个变量，优于哈希表法的 $O(N)$。

6. 易错点 & 调试经验

  • 返回值索引：题目要求 1-indexed，所以返回时记得 +1。
  • 溢出风险：如果 target 非常大，numbers[left] + numbers[right] 可能会导致 int 溢出（虽然本题数据范围通常不会，但工程中要注意）。

7. 相关变式 & 高频延伸题目

  • 相似题：

8. 个人心得 & 复习建议

  • 一句话总结：有序数组找两数，左右夹逼是王道。
  • 对比：一定要清楚这题和 LC 1 的区别，面试必问（有序 vs 无序，空间复杂度差异）。

LeetCode 5. 最长回文子串（Medium）

题目链接：https://leetcode.cn/problems/longest-palindromic-substring/

标签：字符串 | 中心扩散 | 动态规划

所属模块：字符串与动态规划

最后复习日期：2026-02-01

复习次数：1

掌握程度：🌟🌟🌟

1. 题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

  • 输入：s = "babad"
  • 输出："bab" 或 "aba"
  • 示例 2：输入 "cbbd"，输出 "bb"。

2. 核心框架 / 套路归纳

  • 这题最优解是 中心扩散法（Center Expansion）。

  • 适用框架：

    1
    2
    3
    4
    for (int i = 0; i < len; i++) {
        expand(i, i);     // 奇数长度
        expand(i, i + 1); // 偶数长度
    }

  • 为什么用这个框架？ 回文串是中心对称的。枚举所有可能的中心点，向两边扩散，比暴力枚举所有子串 $O(N^3)$ 效率高得多。

3. 思路分析

  1. 暴力思路

    • 两层循环枚举所有子串起点和终点，再加一层循环判断是否回文。
    • 时间复杂度 $O(N^3)$，必超时。

  2. 优化思路（中心扩散）

    • 遍历字符串的每个位置 i。
    • 以 i 为中心扩散（找如 aba 形式的回文）。
    • 以 i 和 i+1 之间的缝隙为中心扩散（找如 abba 形式的回文）。
    • 每次扩散得到的长度如果超过当前最大值，更新结果。

  3. 伪代码

    1
    2
    3
    4
    def extend(left, right):
        while within_bounds and s[left] == s[right]:
            left--, right++
        return s[left+1 : right] # 注意边界处理

4. 代码实现

Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public String longestPalindrome(String s) {
        // 1. 边界防御：空串返回空字符串
        if (s == null || s.length() == 0) return "";
        
        int maxlen = 0;
        String maxString = "";
        
        for (int i = 0; i < s.length(); i++) {
            // 2. 分别尝试以 i 为中心（奇数）和 以 i, i+1 为中心（偶数）
            String s1 = extendString(s, i, i);
            String s2 = extendString(s, i, i + 1);
            
            // 3. 贪心更新：保留最长的
            if (s1.length() > maxlen) {
                maxString = s1;
                maxlen = s1.length();
            }
            if (s2.length() > maxlen) {
                maxString = s2;
                maxlen = s2.length();
            }
        }
        return maxString;
    }

    // 核心助手函数：中心扩散
    private String extendString(String s, int left, int right) {
        // 注意判断顺序：先判断边界 (left >= 0)，再判断字符相等，利用短路防止越界
        while (left >= 0 && right < s.length() && s.charAt(right) == s.charAt(left)) {
            right++;
            left--;
        }
        // substring 是左闭右开
        // 循环结束时 left/right 已指向不匹配的位置（多走了一步）
        // 所以有效范围是 [left+1, right-1]，参数填 (left+1, right)
        return s.substring(left + 1, right);
    }
}

5. 复杂度分析

  • 时间复杂度：$O(N^2)$

    理由：中心点有 $2N-1$ 个（字符+缝隙），每次扩散最坏需 $O(N)$。

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

    理由：只使用了常数变量。（若算上返回的子串对象则是 $O(N)$）。

6. 易错点 & 调试经验

  • 奇偶中心遗漏：只写 extend(i, i) 会漏掉偶数长度回文（如 abba）。
  • substring 索引：while 结束时 left 和 right 都越界了一位，所以 substring 的起始索引是 left + 1，结束索引是 right（因为 Java substring 不包含 end）。
  • 逻辑短路：while 条件里必须先判断 left >= 0 再判断 charAt，否则会报 IndexOutOfBoundsException。

7. 相关变式 & 高频延伸题目

  • 相似题：
    • LC 647. 回文子串（Medium）→ 问有多少个回文子串？核心代码完全一样，只是把 return max 改成 count++。
  • 升级版：
    • Manacher 算法（马拉车）：将时间优化到 $O(N)$，面试通常不强求，但作为加分项。

8. 个人心得 & 复习建议

  • 一句话总结：中心扩散法是解决回文问题的通用钥匙，比 DP 更节省空间，比暴力更快。
  • 快速回顾卡片：
    • 框架：遍历中心，向两边扩。
    • 易错：奇偶中心都要算。
    • 技巧：substring(left+1, right)。