Go back

LeetCode Hot 100——链表篇（反转、合并、环检测、K 个一组翻转）

LeetCode Hot 100 · 链表篇

链表是 Hot 100 里题量最大的一类（14 题），也是面试手撕频率最高的一类——它不考什么高深数据结构，考的全是指针基本功。整类题目翻来覆去只有三个核心套路，吃透它们，14 题全部是套模板：

  1. dummy 虚拟头节点：凡是可能改动头节点（删除、插入、交换、翻转），先 new ListNode(0) 挂上 dummy，边界处理直接清零，返回 dummy.next。
  2. 快慢指针：fast 走两步、slow 走一步，用于找中点、判环、找环入口、找倒数第 N 个。
  3. 三指针原地反转：pre / cur / tmp 三个指针，cur.next = pre 逐步倒转，是 206、234、25 的基石。

下面是本分类所有题目通用的节点定义：

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; }
}

（138 随机链表复制、146 LRU 缓存因题而异，节点定义在对应题内单独给出。）

160. 相交链表

题意

给定两个单链表的头节点 headA、headB，找到并返回它们相交的起始节点；不相交则返回 null。要求不能破坏原链表结构。

输入：listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]
输出：值为 8 的那个节点

题目本质是双指针路径补偿：让两个指针分别遍历两条链表，走完本链表后切换到另一条，这样两者走过的总路程相同，若相交必然在交点相遇。可以类比两人约会——甲走完自己的路后走乙的路，乙走完后走甲的路，两人总路程一样，若有公共路段必然同时到达公共起点。

难点与易错点

解法一：哈希表标记

最直观的思路：先遍历链表 A，把走过的每个节点塞进 HashSet；再遍历链表 B，第一个在集合里出现过的节点就是交点。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 记录链表 A 的所有节点
        Set<ListNode> seen = new HashSet<>();
        ListNode p = headA;
        while (p != null) {
            seen.add(p);
            p = p.next;
        }

        // 遍历 B，第一个出现过的节点即交点
        p = headB;
        while (p != null) {
            if (seen.contains(p)) {
                return p;
            }
            p = p.next;
        }
        return null; // 无交点
    }
}

复杂度：时间 O(m + n)，两链表各遍历一遍；空间 O(m)，哈希表存 A 的全部节点。

瓶颈：空间 O(m)，面试官通常追问「能不能 O(1) 空间」。

解法二：双指针路径补偿（最优）

两个指针 p1、p2 同时从各自头节点出发，每步各走一格；谁先走到 null，就切到另一条链表的头继续走。因为 p1 走的总路程是 A独有 + 公共 + B独有，p2 是 B独有 + 公共 + A独有，两者相等，所以要么在交点相遇，要么同时走到 null。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;

        // 若相交：p1 走 a + c + b，p2 走 b + c + a，在交点相遇
        // 若不相交：两者同时到达 null（a + b == b + a），循环自然结束
        while (p1 != p2) {
            // 走完本链表后，切换到另一条链表的头
            p1 = (p1 == null) ? headB : p1.next;
            p2 = (p2 == null) ? headA : p2.next;
        }

        return p1; // 交点或 null
    }
}

复杂度推导：设 A 独有段长 a、B 独有段长 b、公共段长 c。相交时 p1 走 a + c + b 步、p2 走 b + c + a 步，两者步数相同，所以步数上界为 (a + b + c)，即两链表总长度 → O(m + n)；不相交时各走 a + b 步后同时到 null，同样 O(m + n)。空间只用了两个指针 → O(1)。

多解法对比

解法时间空间适用场景
哈希表标记O(m+n)O(m)快速给出可行解，写起来最不容易错
双指针路径补偿O(m+n)O(1)面试要求的最终答案，思路巧妙

这题约束下（可能很长、且要求 O(1) 空间）双指针是唯一既快又省空间的解，且代码量极短，面试首选。

CodeTop 变体

206. 反转链表

题意

反转一个单链表，返回反转后的头节点。

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

题目本质是三指针原地反转：用 pre、cur、tmp 三个指针，每次把 cur.next 指回 pre，逐步把链表倒转。现实类比是「排队反转」——告诉每个人转身指向身后的人，从头依次操作，队尾最终成为新队首。

难点与易错点

解法一：递归

递归地反转 head.next 之后的子链表，再把 head 挂到子链表末尾。

class Solution {
    public ListNode reverseList(ListNode head) {
        // 递归基：空链表或单节点
        if (head == null || head.next == null) {
            return head;
        }
        // 先递归反转后面的链表，newHead 是反转后的头
        ListNode newHead = reverseList(head.next);
        // 把 head 接到子链表末尾：head.next 是子链表的尾
        head.next.next = head;
        // 关键：断开 head 原来的 next，否则成环
        head.next = null;
        return newHead;
    }
}

复杂度：时间 O(n)，每个节点递归处理一次；空间 O(n)，递归调用栈深度为 n。

瓶颈：递归栈占 O(n) 空间，链表极长时会栈溢出，且不是面试官想要的「O(1) 空间」。

解法二：三指针迭代（最优）

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null; // 前驱，初始 null（反转后成为新链表末尾）
        ListNode cur = head; // 当前处理节点

        while (cur != null) {
            ListNode tmp = cur.next; // 1. 暂存下一节点，防止断链
            cur.next = pre;          // 2. 当前节点指向前驱（反转）
            pre = cur;               // 3. 前驱后移
            cur = tmp;               // 4. 当前节点后移
        }

        return pre; // pre 最终指向新链表的头
    }
}

> **💭 思考**：反转链表的三指针为什么先 `tmp = cur.next`，顺序不能乱？一步步想——递归空间 O(n) 不满足 O(1)，改成迭代后要原地反转，就得在遍历中把每条边的方向倒过来。核心矛盾是：把 `cur.next` 改指 `pre` 的瞬间，原来的 `next` 就断了，`cur` 无法继续前进，所以**必须先用 `tmp` 暂存**。于是形成固定四步：暂存 → 反转 → 前驱后移 → 当前后移。这个「pre/cur/tmp 三指针」是 234、25 等一大类题的基石，背住这四步就够。

复杂度推导：循环变量 cur 从 head 一直走到 null，恰好遍历 n 个节点，每轮只做 4 步常量指针操作 → O(n)；全程只用了 pre、cur、tmp 三个指针，与链表长度无关 → O(1)。

多解法对比

解法时间空间适用场景
递归O(n)O(n)思路简洁，用于理解「链表递归」心智模型
三指针迭代O(n)O(1)面试标准答案，也是 25 题 K 个一组翻转的组件

在「要求 O(1) 空间 + 手撕」的约束下，迭代版是唯一选择，且它会被 92、25 反复复用，必须熟练到能默写。

CodeTop 变体

234. 回文链表

题意

判断一个单链表是否为回文链表（正读反读一样）。

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

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

题目本质是快慢指针找中点 + 反转后半段 + 双指针对比：找到中间，反转后半段，然后从头和后半段头同时向后对比。现实类比是「检查回文词」——找到单词中间位置，把后半部分倒着写，再逐字母和前半段对比。

难点与易错点

解法一：转数组 + 双指针

把链表值逐个放进数组，再用双指针从两端向中间比较，直观且不易错。

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> vals = new ArrayList<>();
        ListNode p = head;
        while (p != null) {
            vals.add(p.val);
            p = p.next;
        }

        int l = 0, r = vals.size() - 1;
        while (l < r) {
            if (!vals.get(l).equals(vals.get(r))) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

复杂度：时间 O(n)，遍历一遍 + 双指针扫一遍；空间 O(n)，数组存全部值。

瓶颈：O(n) 额外空间，面试官一般会要求压到 O(1)。

解法二：快慢指针 + 反转后半段（最优）

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode mid = findMiddle(head);   // 快慢指针找中点
        ListNode head2 = reverseList(mid); // 反转后半段

        // 双指针从两端向中间对比
        ListNode p1 = head, p2 = head2;
        while (p2 != null) { // 后半段更短，用 p2 判终止
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }

    // 快慢指针找链表中间（偶数长度时返回后半段第一个节点）
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 三指针迭代反转（复用 206 模板）
    private ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

复杂度推导：findMiddle 中 fast 走 n 步、slow 走 n/2 步 → O(n)；reverseList 反转后半段 n/2 个节点 → O(n/2)；对比阶段 p2 走 n/2 步 → O(n/2)。三步相加仍是线性 → O(n)。空间只用 slow/fast/pre/cur/p1/p2 等常量个指针 → O(1)。

多解法对比

解法时间空间适用场景
数组 + 双指针O(n)O(n)快速通过、思路直观
快慢指针 + 反转后半段O(n)O(1)面试标准解，考验 206 + 快慢指针组合

在「空间要 O(1)」的约束下只能选反转后半段，且它把「找中点」和「反转」两个高频模板组合在一起，是面试官最爱看的「综合应用」。

CodeTop 变体

141. 环形链表

题意

判断链表中是否有环。

输入：head = [3,2,0,-4], pos = 1（尾部指向第 2 个节点）
输出：true

题目本质是快慢指针追及：若有环，快指针（每步 2 格）必然追上慢指针（每步 1 格）；无环则快指针先到 null。现实类比是「操场跑圈」——两人一快一慢在跑道跑，跑道是环形时快的必然追上慢的，是直道时快的先到终点。

难点与易错点

解法一：哈希表

遍历节点，把访问过的节点存进 HashSet，遇到重复节点即有环。

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        ListNode p = head;
        while (p != null) {
            if (seen.contains(p)) {
                return true; // 再次遇到同一节点，说明有环
            }
            seen.add(p);
            p = p.next;
        }
        return false;
    }
}

复杂度：时间 O(n)，最多遍历 n 个节点；空间 O(n)，哈希表存所有节点。

瓶颈：O(n) 空间，有环时无法提前结束，且不是 O(1) 的最优解。

解法二：快慢指针（最优）

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        // fast 每次走两步，slow 每次走一步；有环则 fast 必然追上 slow
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true; // 快慢相遇，确认有环
            }
        }

        return false; // fast 到达末尾，无环
    }
}

复杂度推导：无环时，fast 走到 null 共走 n 步 → O(n)。有环时，slow 入环前最多走 n 步；入环后 fast 与 slow 距离不超过环长 L，相对速度 1，最多再走 L 步相遇；L ≤ n，所以总步数仍 ≤ 2n → O(n)。空间只用两个指针 → O(1)。

多解法对比

解法时间空间适用场景
哈希表O(n)O(n)直观，但浪费空间
快慢指针（Floyd）O(n)O(1)面试标准解，且是 142 的前置

这题约束下快慢指针是唯一 O(1) 空间的解，而且它直接通向 142（找环入口），务必记住「相对速度 1」这个相遇证明。

CodeTop 变体

142. 环形链表 II

题意

返回链表开始入环的第一个节点；无环返回 null。不允许修改链表。

输入：head = [3,2,0,-4], pos = 1
输出：值为 2 的那个节点（索引 1）

题目本质是快慢指针 + 数学推导：设头到入环点距离为 a，入环点到相遇点距离为 b，相遇时 fast 走了 2(a+b) = a+b + n*环长，可推出 a = n*环长 - b，即从头出发和从相遇点出发的两个指针同速走 a 步后，会在入环点相遇。现实类比是「绳子打结」——先用一快一慢两只虫确认有结，再分别从头和结点处同速爬，相遇处就是打结位置。

难点与易错点

解法一：哈希表

和 141 哈希表版几乎一样，只是返回「第一个重复出现的节点」。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        ListNode p = head;
        while (p != null) {
            if (seen.contains(p)) {
                return p; // 第一次重复访问的节点就是入环点
            }
            seen.add(p);
            p = p.next;
        }
        return null;
    }
}

复杂度：时间 O(n)；空间 O(n)。

瓶颈：O(n) 空间，且没有体现「Floyd 判环」的数学价值。

解法二：快慢指针 + 数学推导（最优）

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;

        // 阶段一：快慢指针找相遇点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                // 阶段二：一个从头、一个从相遇点，同速前进，在入环点相遇
                // 数学推导：设头到入环点距离 a，入环点到相遇点距离 b，
                // fast 路程 = a + b + n*环长 = 2*(a + b) → a = n*环长 - b
                // 故 index2 从头走 a 步、index1 从相遇点走 a 步，必在入环点相遇
                ListNode index1 = fast;   // 从相遇点出发
                ListNode index2 = head;   // 从头出发
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1; // 入环点
            }
        }

        return null; // 无环
    }
}

> **💭 思考**：为什么「判环」用快慢指针，「找环入口」还要再来一个阶段？一步步想——快慢指针相遇只能证明有环，相遇点在环内、不一定是入口。要定位入口，需要从「相遇」这个信息里反推：设头到入口为 a、入口到相遇点为 b，快指针路程是慢指针 2 倍，可得 `a = n×环长 - b`，即「从头走 a 步」和「从相遇点走 a 步」会同时到达入口。于是第二阶段：一个指针回到头、一个留在相遇点，同速前进，再次相遇处就是入口。这解释了为什么 142 比 141 多一段「同速再走」，本质是把判环结论转成位置信息。

复杂度推导：阶段一无环时 fast 走 n 步到 null → O(n)；有环时 slow 入环前 ≤ n 步、入环后 ≤ L 步追上 → O(n)。阶段二 index2 从 head 走 a 步（a < n）→ O(n)。两阶段相加仍线性 → O(n)。空间只用 fast/slow/index1/index2 常量个指针 → O(1)。

数学推导补充（口述要点）：设头到入口 a，入口到相遇点 b，相遇点到入口 c。相遇时 slow 走了 a + b，fast 走了 a + b + n(b + c)（多绕 n 圈）。因为 fast 速度是 2 倍，2(a+b) = a + b + n(b+c) → a + b = n(b+c) → a = n(b+c) - b = (n-1)(b+c) + c。所以从头走 a 步和从相遇点走 a 步，都等价于「绕 (n-1) 圈再多走 c」，两者在入口相遇。

多解法对比

解法时间空间适用场景
哈希表O(n)O(n)快速可行，但没亮点
快慢指针 + 数学O(n)O(1)面试标准解，考的是数学推导能力

这题约束下快慢指针 O(1) 空间是唯一选择，且数学推导是面试官区分「背题」和「理解」的关键，务必能完整口述。

CodeTop 变体

21. 合并两个有序链表

题意

把两个升序链表合并成一个升序链表，由原节点拼接而成。

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

题目本质是双指针归并：类似归并排序的 merge 步骤，每次从两个链表头部取较小值拼到结果链表，一条遍历完就把另一条剩余部分整体接上。现实类比是「两队排好序的人合并成一队」——每次比较两队队首，较矮的先进新队，某队空后把另一队全加到末尾。

难点与易错点

解法一：递归

递归比较两个头，取较小者，其 next 指向「剩余两链表的合并结果」。

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;
        }
    }
}

复杂度：时间 O(m + n)，每次递归处理掉一个节点；空间 O(m + n)，递归栈深度。

瓶颈：递归栈 O(m+n) 空间，链表长时可能栈溢出。

解法二：迭代 + dummy（最优）

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1); // 虚拟头，简化结果链表头部处理
        ListNode p = dummy;                // p 始终指向已合并链表的最后一个节点

        ListNode p1 = list1, p2 = list2;
        while (p1 != null && p2 != null) {
            // 每次选较小节点拼到 p 后面
            if (p1.val <= p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }

        // 剩余节点已有序，整体接上
        p.next = (p1 != null) ? p1 : p2;

        return dummy.next;
    }
}

复杂度推导：循环每轮让 p1 或 p2 前进一步，两个指针合计移动 m + n 次，每轮 O(1) → O(m + n)；只用了 dummy、p、p1、p2 常量个指针 → O(1)。

多解法对比

解法时间空间适用场景
递归O(m+n)O(m+n)代码简洁，理解递归合并
迭代 + dummyO(m+n)O(1)面试标准解，且是 148、23 的组件

在「要求 O(1) 空间」约束下选迭代版；且 mergeTwoLists 会被 148（排序链表）、23（合并 K 个）直接复用，要练到盲写。

CodeTop 变体

2. 两数相加

题意

两个非空链表各表示一个非负整数，按逆序存储（每节点存一位数字），把两数相加，以同样的链表形式返回和。

输入：l1 = [2,4,3], l2 = [5,6,4]   （即 342 + 465）
输出：[7,0,8]                       （即 807）

题目本质是模拟手工加法：从低位到高位逐位相加，处理进位 carry，用 dummy 构建结果链表，最后检查最高位进位。现实类比是「小学竖式加法」——从个位到高位逐位相加，满十进一，一位一位地构建结果。

难点与易错点

解法一：转大数相加（直观但非最优）

把两个链表读成字符串，用 BigInteger 相加，再拆回链表。它正确、直观，能躲过 int 溢出，但空间 O(n)、且绕开了「进位」的考点，面试不推荐。

import java.math.BigInteger;

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 读逆序数字为字符串
        StringBuilder s1 = new StringBuilder();
        for (ListNode p = l1; p != null; p = p.next) s1.insert(0, p.val);
        StringBuilder s2 = new StringBuilder();
        for (ListNode p = l2; p != null; p = p.next) s2.insert(0, p.val);

        // 大数相加（避免 long 溢出）
        BigInteger sum = new BigInteger(s1.toString()).add(new BigInteger(s2.toString()));

        // 拆回逆序链表
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        String str = sum.toString();
        for (int i = str.length() - 1; i >= 0; i--) {
            p.next = new ListNode(str.charAt(i) - '0');
            p = p.next;
        }
        return dummy.next;
    }
}

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

瓶颈：O(n) 额外空间，且没体现逐位进位的精髓，面试官要的是下面的模拟解。

解法二：逐位模拟加法（最优）

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        int carry = 0; // 进位

        // 同时遍历两条链表（某条为 null 时视其值为 0），并处理最后的进位
        while (l1 != null || l2 != null || carry != 0) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;

            int sum = val1 + val2 + carry;
            carry = sum / 10;              // 更新进位
            p.next = new ListNode(sum % 10); // 当前位数字
            p = p.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        return dummy.next;
    }
}

复杂度推导：设两链表长度 m、n（m ≥ n）。循环迭代次数 = max(m, n) 次「同时遍历」+ 最多 1 次「纯 carry」收尾，每轮 O(1) → O(max(m, n))。空间上，结果链表长度最多 max(m, n) + 1（最高位进位多一个节点），这是输出本身 → 若不计输出则额外 O(1)，计输出则 O(max(m, n))。

多解法对比

解法时间空间适用场景
转 BigIntegerO(m+n)O(m+n)快速绕开溢出，但偏离考点
逐位模拟加法O(max(m,n))O(max(m,n))面试标准解，考进位处理

这题约束下「逐位模拟」是唯一能同时保证正确性（不溢出）与 O(1) 额外空间（除输出外）的写法，进位细节是面试扣分重灾区。

CodeTop 变体

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

题意

删除链表的倒数第 n 个节点，返回新链表头。

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

题目本质是双指针保持固定间距：fast 先走 n + 1 步，再和 slow 同步前进，fast 到 null 时 slow 恰在待删节点的前驱。现实类比是「两人排队保持固定距离」——后面的人与前面的人保持固定距离，前面的人走到终点时，后面的人恰好在需要的位置。

难点与易错点

解法一：两次遍历（先求长度）

先统计链表总长 len，则倒数第 n 个就是正数第 len - n + 1 个，再从头走到它的前驱删除。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 第一次遍历：求长度
        int len = 0;
        for (ListNode p = head; p != null; p = p.next) {
            len++;
        }

        // 第二次遍历：定位到待删节点的前驱
        ListNode p = dummy;
        for (int i = 0; i < len - n; i++) {
            p = p.next;
        }

        p.next = p.next.next; // 删除
        return dummy.next;
    }
}

复杂度：时间 O(n)，两遍遍历；空间 O(1)。

瓶颈：要遍历两遍，面试官常追问「能不能一遍」。

解法二：双指针一遍扫描（最优）

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head; // 处理删除头节点的边界

        ListNode fast = dummy;
        ListNode slow = dummy;

        // fast 先走 n+1 步，使 fast、slow 间隔 n 个节点，slow 落在待删节点前驱
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // 同步前进：fast 到 null 时 slow 恰在待删节点的前驱
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        slow.next = slow.next.next; // 跳过待删节点
        return dummy.next;
    }
}

复杂度推导：第一阶段 fast 走 n + 1 步；第二阶段 fast 继续从 n+1 位置走到 null，共走 len + 1 - (n+1) = len - n 步，slow 同步走 len - n 步。两步合计 (n+1) + (len-n) = len + 1 次前进，每步 O(1) → O(n)；只用了 dummy/fast/slow 常量指针 → O(1)。

多解法对比

解法时间空间适用场景
两次遍历O(n)O(1)直观，先求长度再定位
双指针一遍O(n)O(1)面试标准解，双指针固定间距的典范

在「要求一遍扫描」的约束下选双指针；「快指针先走固定步数制造间距」这个模板在找倒数第 k 个、判环等多题通用。

CodeTop 变体

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

题意

两两交换相邻节点，返回新头。只能交换节点（不能改值）。

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

题目本质是模拟指针交换：每次处理一对节点，保存三个关键临时变量后按顺序重连，cur 移动到已交换对的末尾以处理下一对。现实类比是「两人换座位」——记录座位旁下一对人，让两人换完，下一对同样操作。

难点与易错点

解法一：递归

递归交换「前两个节点 + 剩余子链表的交换结果」。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head; // 不足一对，直接返回
        }

        ListNode second = head.next;      // 第二个节点将成为新头
        head.next = swapPairs(second.next); // 第一个节点指向剩余子链表的交换结果
        second.next = head;               // 第二个节点指向第一个
        return second;
    }
}

复杂度：时间 O(n)，每层处理一对；空间 O(n)，递归栈深度 n/2。

瓶颈：递归栈 O(n)，且链表长时栈溢出。

解法二：迭代 + dummy（最优）

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;

        // 每次处理 cur 后面的一对节点
        while (cur.next != null && cur.next.next != null) {
            ListNode first  = cur.next;      // 待交换的第一个节点
            ListNode second = cur.next.next; // 待交换的第二个节点
            ListNode tmp    = second.next;   // 保存后续节点，防止断链

            // 重连：cur → second → first → tmp
            cur.next    = second;
            second.next = first;
            first.next  = tmp;

            // cur 移到已交换对的末尾（first），准备处理下一对
            cur = first;
        }

        return dummy.next;
    }
}

复杂度推导：每轮交换一对（2 个节点），共 n/2 轮，每轮 O(1) 指针操作 → 总 O(n)；只用 dummy/cur/first/second/tmp 常量个指针 → O(1)。

多解法对比

解法时间空间适用场景
递归O(n)O(n)思路清晰，代码短
迭代 + dummyO(n)O(1)面试标准解，且是 25 题 k=2 的特例

这题是 25（K 个一组翻转）当 k=2 时的特例，迭代写法里的「保存三个临时变量 + 顺序重连」是 25 的基础，务必吃透。

CodeTop 变体

25. K 个一组翻转链表

题意

每 k 个节点一组翻转，剩余不足 k 个则保持原有顺序，返回修改后的链表。

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

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

题目本质是分组反转 + 拼接：统计节点总数，每次对 k 个节点做标准反转，再把反转后的组正确拼接到前一组末尾，循环直到剩余不足 k。现实类比是「按组反向排队」——把整队按 k 个一组分组，每组内部倒序站，不足一组的原序，各组串联成新队伍。

难点与易错点

解法一：递归

先判断剩余是否够 k 个；够则反转前 k 个，剩余递归处理；不够则直接返回。

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 检查剩余节点是否够 k 个，不够则原样返回
        ListNode p = head;
        for (int i = 0; i < k; i++) {
            if (p == null) return head;
            p = p.next;
        }

        // 反转前 k 个节点（复用 206 模板）
        ListNode pre = null, cur = head;
        for (int i = 0; i < k; i++) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }

        // 原 head 现在是组尾，接上后续递归反转的结果
        head.next = reverseKGroup(cur, k);
        return pre; // 新组头
    }
}

复杂度：时间 O(n)，每个节点被访问常数次；空间 O(n/k)，递归栈深度约 n/k。

瓶颈：递归栈 O(n/k)，且拼接思路藏在递归里，迭代版更能体现「手撕」功底。

解法二：迭代分组（最优）

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 统计链表长度
        int n = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            n++;
        }

        ListNode dummy = new ListNode(0, head);
        ListNode p = dummy; // p 始终指向当前待处理组的前驱节点

        // 每次处理 k 个节点
        for (; n >= k; n -= k) {
            ListNode pre = null;
            ListNode cur = p.next; // 当前组的第一个节点

            // 标准链表翻转：翻转 k 个节点
            for (int i = 0; i < k; i++) {
                ListNode nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            }

            // 翻转后：pre 是新组头，p.next（原头）是新组尾
            ListNode groupTail = p.next; // 原头成为翻转后的组尾
            p.next.next = cur;           // 新组尾连接下一组的头
            p.next = pre;                // p 的下一个改为新组头（pre）
            p = groupTail;               // p 移到当前组末尾，准备下一组
        }

        return dummy.next;
    }
}

复杂度推导：① 统计长度遍历 n 个节点 → O(n)。② 分组翻转：共 n/k 组，每组内 k 次循环反转，合计 (n/k) * k = n 次操作 → O(n)。③ 拼接：每组 O(1)，共 n/k 组 → O(n/k)。三段相加仍是线性 → O(n)。空间只用 dummy/p/pre/cur/nxt/groupTail 常量个指针 → O(1)。

多解法对比

解法时间空间适用场景
递归O(n)O(n/k)代码简洁，逻辑清晰
迭代分组O(n)O(1)面试标准解，拼接细节最见功底

在「要求 O(1) 空间 + 手撕拼接」约束下选迭代版。它是链表题的「集大成者」——dummy + 三指针反转 + 分组拼接全用上了，字节、腾讯几乎必考。

CodeTop 变体

138. 随机链表的复制

题意

给定链表，每个节点含 val、next、random（可指向任意节点或 null），构造并返回它的深拷贝。

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：与输入结构完全一致的新链表（每个节点都是新对象）

本题节点定义（含 random 指针）：

class Node {
    int val;
    Node next;
    Node random;
    Node(int val) { this.val = val; }
}

题目本质是原地拼接复制节点绕过哈希表：在每个原节点后插入它的复制节点，利用这种结构处理 random（cur.random.next 就是 cur.random 的复制节点），最后拆分两条链表。现实类比是「档案复制」——在每份档案旁放一份复印件，先复印原件，再按原件的引用关系找到复印件的引用，最后把原件和复印件分开归档。

难点与易错点

解法一：哈希表映射

第一遍遍历创建所有新节点并存入 HashMap<旧节点, 新节点>；第二遍根据映射设置 next 和 random。

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        // 第一遍：为每个旧节点创建新节点，建立映射
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        // 第二遍：依据映射设置 next 和 random
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }
}

复杂度：时间 O(n)，两遍遍历；空间 O(n)，哈希表存 n 个映射。

瓶颈：O(n) 额外空间。面试官常追问「能不能 O(1) 空间」，引出下面的原地拼接。

解法二：原地拼接（最优，O(1) 额外空间）

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        // 第一步：在每个原节点后插入其复制节点
        Node cur = head;
        while (cur != null) {
            Node copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
            cur = copy.next; // 跳到下一个原节点
        }

        // 第二步：设置复制节点的 random
        // cur.next 是复制节点，cur.random.next 是 random 对应的复制节点
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next; // 跳到下一个原节点
        }

        // 第三步：拆分原链表与复制链表
        Node newHead = head.next;
        cur = head;
        while (cur != null) {
            Node copy = cur.next;                                  // 当前原节点的复制节点
            cur.next = copy.next;                                  // 恢复原链表
            copy.next = (copy.next != null) ? copy.next.next : null; // 复制链表指向下一个复制节点
            cur = cur.next;                                        // 移动到下一个原节点
        }

        return newHead;
    }
}

复杂度推导：三步各遍历一遍链表，每遍 n 个节点，每节点 O(1) → 3n → O(n)。空间上只用了 cur/copy/newHead 常量个指针，不额外开哈希表 → O(1)（新链表本身是输出，不计入额外空间）。

多解法对比

解法时间空间适用场景
哈希表映射O(n)O(n)直观、不易错，两遍遍历
原地拼接O(n)O(1)面试标准解，考「复用 next 当映射」的巧思

在「要求 O(1) 空间」约束下选原地拼接。这个「把复制节点塞进原链表的 next 里当隐式映射」的技巧非常巧，字节、腾讯爱考，且能自然过渡到「图的深拷贝」。

CodeTop 变体

148. 排序链表

题意

给链表按升序排序并返回。

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

题目本质是链表版归并排序：找到中间节点把链表一分为二，递归排序左右两段，再 merge 合并。现实类比是「图书馆整理书架」——把书架从中间分开，左右各请人整理好，你再合并两组有序书目。

难点与易错点

解法一：转数组排序

把节点值取出排序，再写回链表——O(n log n) 时间但 O(n) 空间，且不满足「链表排序」的考察意图。

class Solution {
    public ListNode sortList(ListNode head) {
        List<Integer> vals = new ArrayList<>();
        ListNode p = head;
        while (p != null) {
            vals.add(p.val);
            p = p.next;
        }

        Collections.sort(vals); // 快排 O(n log n)

        p = head;
        for (int v : vals) {
            p.val = v;
            p = p.next;
        }
        return head;
    }
}

复杂度：时间 O(n log n)（sort）；空间 O(n)（数组）。

瓶颈：O(n) 额外空间，且这本质是「数组排序」，绕开了链表归并的考点。

解法二：归并排序（最优，自顶向下）

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head; // 递归基：空或单节点已有序
        }

        // 找中点并断开左右两段
        ListNode mid = findMiddle(head);
        ListNode left  = sortList(head); // 左段
        ListNode right = sortList(mid);  // 右段

        return mergeSorted(left, right);
    }

    // 快慢指针找中点，并把左段尾指向 null 断开
    private ListNode findMiddle(ListNode head) {
        ListNode pre = head, slow = head, fast = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null; // 断开左段
        return slow;     // slow 是右半段头
    }

    // 归并两个有序链表（复用 21 题模板）
    private ListNode mergeSorted(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

复杂度推导：归并排序每次把区间对半分，递归深度为 log₂n 层；每一层对所有节点做一次 mergeSorted，单层合计 O(n)；总时间 = 层数 × 单层 = log n × n → O(n log n)。空间：递归调用栈深度 log n，每层 O(1) → O(log n)（归并过程只改指针，不需要像数组归并那样开临时数组，这正是链表归并的优越性）。

多解法对比

解法时间空间适用场景
转数组排序O(n log n)O(n)快速通过，但偏离考点
归并（自顶向下）O(n log n)O(log n)面试标准解
归并（自底向上）O(n log n)O(1)严格 O(1) 空间的进阶解

这题约束「O(n log n) 时间、O(1) 空间（最严格）」下，链表归并是唯一出路：数组归并需要 O(n) 临时数组，而链表归并改指针即可，天然省空间。

CodeTop 变体

23. 合并 K 个升序链表

题意

给定一个链表数组，每个链表已升序，把所有链表合并成一个升序链表。

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

题目本质是小顶堆优先队列多路归并：把所有链表头节点放入小顶堆，每次取出最小节点拼接到结果，该节点有后继就把后继入堆。现实类比是「K 路归并」——K 组有序播放列表，每次从各组当前队首选最小歌曲播放，播完把下一首加入候选池（优先队列）。

难点与易错点

解法一：两两顺序合并

用 21 题的 mergeTwoLists 逐个合并：res = merge(res, lists[i])。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        ListNode res = null;
        for (ListNode list : lists) {
            res = mergeTwoLists(res, list); // 复用 21 题
        }
        return res;
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) { p.next = l1; l1 = l1.next; }
            else                  { p.next = l2; l2 = l2.next; }
            p = p.next;
        }
        p.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

复杂度：第 i 次合并时结果长度约 i * (n/k)，总时间 ∑ i·(n/k) ≈ O(n·k)；空间 O(1)。

瓶颈：O(n·k) 时间——前几轮反复扫描前面已合并的大链表，k 大时明显慢。

解法二：小顶堆优先队列（最优）

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;

        // 小顶堆：按节点值升序排列
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
            lists.length, (a, b) -> a.val - b.val
        );

        // 将所有非 null 的链表头节点加入小顶堆
        for (ListNode head : lists) {
            if (head != null) {
                minHeap.offer(head);
            }
        }

        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;

        while (!minHeap.isEmpty()) {
            ListNode smallest = minHeap.poll(); // 取出当前最小节点
            p.next = smallest;
            p = p.next;

            // 若该节点还有后继，将后继入堆继续参与比较
            if (smallest.next != null) {
                minHeap.offer(smallest.next);
            }
        }

        return dummy.next;
    }
}

> **💭 思考**：合并 K 个有序链表为什么用「小顶堆」，而不是两两顺序合并？一步步想——两两顺序合并的瓶颈是「每次找当前最小值都要在所有 k 个链表头里扫一遍」，第 i 次合并时反复扫描前面已合并的大链表，总时间 O(n·k)。而「每次从 k 个头里取最小」正是优先队列的典型场景：堆里始终只放 k 个候选头，取出最小后把它的后继入堆，每次取最小从 O(k) 降到 O(log k)，整体 O(n log k)。看到「多路归并、反复取最小」，就该想到小顶堆。

复杂度推导：设总节点数 n = 所有链表长度之和。每个节点入堆一次、出堆一次，共 2n 次堆操作；堆中元素数量始终 ≤ k（poll 一个最多 offer 一个），每次堆操作 O(log k)；总时间 = 2n × O(log k) = O(n log k)。空间上堆里最多同时存 k 个节点 → O(k)。

多解法对比

解法时间空间适用场景
两两顺序合并O(n·k)O(1)k 很小时简单可行
分治归并O(n log k)O(log k)k 大且不想用堆时
小顶堆优先队列O(n log k)O(k)面试标准解，最通用

这题约束下（k 可能很大）优先队列把「每次找最小值」从 O(k) 降到 O(log k)，是 k 路归并的经典答案；分治归并（两两配对合并）也是 O(n log k)，可作补充。

CodeTop 变体

146. LRU 缓存

题意

设计并实现 LRU（最近最少使用）缓存：get(key) O(1) 返回值，不存在返回 -1；put(key, value) O(1) 插入/更新，容量满时逐出最久未使用的 key。

输入：
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出：
[null, null, null, 1, null, -1, null, -1, 3, 4]

题目本质是哈希表 + 双向链表：哈希表提供 O(1) key 查询，双向链表维护访问顺序（最近访问移到头部，最久未使用在尾部，满时淘汰尾部）。现实类比是「图书馆最受欢迎书架」——书架容量有限，记录每本书最近借出顺序，借出就把它移到最前面，架子满了就把最后面（最久没人借）的书撤走。

说明：LeetCode 上本题类名固定为 LRUCache（构造器签名 LRUCache(int capacity)），其余 13 题类名统一为 Solution。这里沿用官方签名。

难点与易错点

解法一：LinkedHashMap（Java 内置，直观）

Java 的 LinkedHashMap 在构造时指定 accessOrder=true 即可按访问顺序维护，removeEldestEntry 重写实现容量淘汰。

import java.util.LinkedHashMap;
import java.util.Map;

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    public LRUCache(int capacity) {
        // accessOrder = true：按访问顺序（最近访问移到末尾）
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; // 超过容量淘汰最老元素
    }
}

复杂度：get/put 均 O(1)（LinkedHashMap 内部就是哈希表 + 双向链表）。空间 O(capacity)。

瓶颈：这是「调库」，面试官不会满意——要的是手写哈希表 + 双向链表证明你懂底层。

解法二：哈希表 + 双向链表（手撕，最优）

class LRUCache {
    private final int capacity;
    // 哨兵节点：dummy.next 是最近使用，dummy.pre 是最久未使用
    private final Node dummy = new Node(0, 0);
    private final Map<Integer, Node> map = new HashMap<>();

    // 双向链表节点
    private class Node {
        int key, value;
        Node pre, next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        // 初始化循环双向链表（哨兵节点自环）
        dummy.pre = dummy;
        dummy.next = dummy;
    }

    public int get(int key) {
        Node node = getNode(key);
        return node == null ? -1 : node.value;
    }

    public void put(int key, int value) {
        Node node = getNode(key);
        if (node != null) {
            node.value = value; // 更新值（getNode 中已移到头部）
            return;
        }

        // 新节点：插入到链表头部
        node = new Node(key, value);
        map.put(key, node);
        insertToFront(node);

        // 超过容量：逐出最久未使用节点（dummy.pre）
        if (map.size() > capacity) {
            Node lru = dummy.pre;
            map.remove(lru.key);
            removeNode(lru);
        }
    }

    // 从 map 获取节点，并移到链表头部（标记为最近使用）
    private Node getNode(int key) {
        if (!map.containsKey(key)) return null;
        Node node = map.get(key);
        removeNode(node);    // 从当前位置摘除
        insertToFront(node); // 插到链表头部
        return node;
    }

    // 从双向链表中摘除节点
    private void removeNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    // 将节点插入到链表头部（dummy.next 之前）
    private void insertToFront(Node node) {
        node.pre = dummy;
        node.next = dummy.next;
        node.pre.next = node;
        node.next.pre = node;
    }
}

> **💭 思考**：为什么 LRU 必须「哈希表 + 双向链表」，缺一个都不行？一步步想——get/put 都要 O(1)，key 的定位靠哈希表 O(1) 查找；但「淘汰最久未使用」需要维护一个访问顺序，且插入/删除要 O(1)。单向链表删除中间节点要先遍历找前驱，是 O(n)，做不到；只有双向链表能 O(1) 摘除任意节点，配合哈希表 O(1) 定位，才能同时满足「O(1) 查询 + O(1) 移动」。哈希表管「在哪」、双向链表管「顺序」，两者组合是这题唯一解。

复杂度推导：get = HashMap 定位 O(1) + 双向链表摘除 O(1) + 插入头部 O(1) = O(1)；put 的插入、更新、淘汰各步都是 O(1) 的 map 操作 + 链表操作 = O(1)。空间：map + 链表最多存 capacity 个节点 → O(capacity)。

多解法对比

解法时间空间适用场景
LinkedHashMapO(1)O(capacity)快速实现，说明思路
哈希表 + 双向链表O(1)O(capacity)面试标准手撕，考底层实现

这题是「哈希表提供 O(1) 定位 + 双向链表提供 O(1) 移动」组合拳的教科书案例，字节、腾讯、阿里、美团几乎逢面必考，必须能独立盲写并解释每个字段。

CodeTop 变体

以上就是 Hot 100 链表篇的全部 14 题。整类题目可以浓缩成一句话：dummy 管边界、快慢指针管定位、三指针管反转，剩下的合并、相加、复制、排序、缓存，都是这三个模板的组合与放大。手撕前把 206（反转）、141/142（快慢指针）、21（归并）、146（哈希 + 双链）这五道练到盲写，其余九题自然水到渠成。

章末提问

链表篇的追问多集中在「为什么选这个解法 / 复杂度怎么推 / 边界怎么抠」这类思考型问题。下面是最常考的 5 个角度（结论先行，因为跟着原因）：

  1. 「为什么链表题这么多都挂一个 dummy 节点？不挂行不行？」 回答思路：结论是挂 dummy 能用统一逻辑消除「改头节点」的边界特判，因为删除、插入、交换、翻转都可能改动头节点，不挂就得对 head 单独写 if，挂了之后一律返回 dummy.next，代码更短且更不容易错。

  2. 「反转链表递归和迭代你都会，面试时到底选哪个？」 回答思路：结论是默认迭代三指针，因为它是 O(1) 空间、不会栈溢出，而且会被 92、25 反复复用；递归只在对方明确要求或想展示「链表递归心智模型」时才写，且要主动补一句「递归栈是 O(n) 空间」。

  3. 「快慢指针的复杂度你怎么推到 O(n)？」 回答思路：结论是无环时 fast 走 n 步到 null；有环时 slow 入环前最多走 n 步、入环后 fast 与 slow 距离不超过环长 L、相对速度是 1，最多再走 L 步就追上，因为 L ≤ n，所以总步数仍 ≤ 2n，即 O(n)。

  4. 「21、23、148 这些合并、排序题，为什么迭代 + dummy 比递归更被认可？」 回答思路：结论是递归栈会占 O(n) 或 O(log n) 空间，而迭代 + dummy 只用常数个指针、空间 O(1)，因为合并类题目的本质是顺序扫描 + 拼接，用循环就能表达，并不需要递归的回溯能力。

  5. 「LRU 为什么必须是哈希表 + 双向链表，用单向链表差在哪？」 回答思路：结论是单链表删除中间节点要 O(n) 找前驱、做不到 O(1)，因为 LRU 要求 get 和 put 都 O(1)，只有双向链表能 O(1) 摘除节点、哈希表能 O(1) 定位节点，两者组合才能同时满足。

Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
字母异位词分组——HashMap处理集合分组的经典模式
Next Post
合并K个升序链表——小顶堆与分治归并