CS-Notes Leetcode 题解详解：链表十大经典问题的思路、实现与变体

链表是单指针线性结构，每个节点只保存一个值和一个指向下一个节点的指针，这种"头尾相接、只进不出"的特点决定了绝大多数链表问题都可以用递归来表达。本篇基于 CS-Notes 仓库中 Leetcode 题解 - 链表 一文，完整继承并展开其中十道经典题目——交点、反转、归并、去重、删除倒数第 n 个、相邻交换、求和、回文、分隔、奇偶聚集——给出可运行的 Java 实现，并结合仓库内 剑指 Offer 题解 系列中对同一知识点的多解实现，补足迭代与递归两种视角、头结点辅助技巧与双指针数学推导，帮助你形成"一套指针操作范式"的完整能力。

链表问题的总纲：递归与指针

原文开篇给出一句总纲："链表是空节点，或者有一个值和一个指向下一个链表的指针，因此很多链表问题可以用递归来处理。" 这句话是理解整篇题解的钥匙。

从递归视角看，一个链表可以拆成"头节点 + 头节点之后的子链表"，而"头节点之后的子链表"本身又是一个链表，于是可以用同一套逻辑自底向上地求解：先解决子问题，再把头节点拼回去。十道题中有四道（反转、归并、去重、以及回文中的一段）都直接采用了这种"先递归处理尾部、再回头连接"的写法。

从指针视角看，几乎所有链表原地操作都依赖一个通用套路：维护一个"前驱指针"或"头结点（dummy node）"来暂存断开的链表头，避免在修改 next 指针时丢失后续节点。仓库中 从尾到头打印链表 一篇专门用头插法讲清了这一点——引入一个不存值的头结点，让插入操作永远发生在"头部"，从而把正序链表变成逆序链表。这个头结点技巧在本文第 2、6、7、8 题中反复出现。

下面逐题展开。

1. 找出两个链表的交点

对应 LeetCode 160. Intersection of Two Linked Lists（Easy）。

题目约束：时间复杂度 O(N)、空间复杂度 O(1)；若不存在交点返回 null。

先明确"交点"的几何含义。由于每个节点只有一个 next 指针、也就只能有一个后继，所以两个链表相交后一定是"尾部公共"的 Y 形结构，例如 A 和 B 相交于 c1：

A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗
B:    b1 → b2 → b3

而不会出现一个节点分叉出两个后继的情况，因为那样违反了单指针链表定义。

核心思路是双指针"错位对齐"。设 A 的长度为 a + c、B 的长度为 b + c，其中 c 是尾部公共部分长度，那么恒有 a + c + b = b + c + a。做法是：访问 A 的指针走到尾部后改从 B 的头部继续，访问 B 的指针走到尾部后改从 A 的头部继续。这样两个指针走过的总步数相同，必然同时到达交点。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode l1 = headA, l2 = headB;
    while (l1 != l2) {
        l1 = (l1 == null) ? headB : l1.next;
        l2 = (l2 == null) ? headA : l2.next;
    }
    return l1;
}

这段代码优雅地处理了"无交点"的边界：若两链表不相交，则 a + b = b + a，两个指针会同时变成 null，循环自然退出并返回 null，不会死循环。

仓库中 剑指 Offer 52. 两个链表的第一个公共结点 用 FindFirstCommonNode 给出了同一套双指针解法，两者逻辑完全一致，可对照阅读。

原文还补充了一个"退化版"问题：如果只判断是否存在交点而不要求返回交点，有两种更简单的解法——其一，把第一个链表尾部接到第二个链表头部，然后判断第二个链表是否成环（可套用下文第 8 题的回文/找环相关的双指针）；其二，直接比较两个链表的最后一个节点是否相同。后者最直观：若存在交点，尾部公共段必然意味着两个链表末节点是同一个对象。

2. 链表反转

对应 LeetCode 206. Reverse Linked List（Easy）。这是链表最基础的原地操作，本文给出递归与头插法两种实现。

递归法。 先递归地把 head.next 之后的链表反转，再把 head 接到反转后子链表的尾部并断开 head.next：

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode next = head.next;
    ListNode newHead = reverseList(next);
    next.next = head;
    head.next = null;
    return newHead;
}

这里 next.next = head; head.next = null; 两句是原地反转的关键：把后继节点的回指针指向当前节点，同时清空当前节点对后继的引用，防止成环。

头插法（迭代）。 维护一个虚拟头结点 newHead，把原链表的每个节点依次"摘下来"插到 newHead 后面，每次插入都让被摘节点成为新链表头部，从而天然实现整体逆序：

public ListNode reverseList(ListNode head) {
    ListNode newHead = new ListNode(-1);
    while (head != null) {
        ListNode next = head.next;
        head.next = newHead.next;
        newHead.next = head;
        head = next;
    }
    return newHead.next;
}

仓库中 剑指 Offer 24. 反转链表 提供了 ReverseList 的递归与迭代两版实现，其中迭代版使用的正是上述头插法（用 newList 作为头结点、head.next = newList.next; newList.next = head; 两步完成插入），两处的插入顺序细节一致，可作为交叉印证。

3. 归并两个有序的链表

对应 LeetCode 21. Merge Two Sorted Lists（Easy）。

原文给出的是一版非常紧凑的递归实现：比较两个头节点，较小者作为新的头节点，其 next 递归地合并"剩余部分"：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

两个基线 l1 == null return l2 / l2 == null return l1 保证了当其中一条链表耗尽时，直接把另一条的剩余部分接到结果末尾，无需额外处理。

仓库中 剑指 Offer 25. 合并两个排序的链表 同时给出了递归与迭代两种写法。其递归版与本文几乎相同（用 list1.val <= list2.val 判定，<= 保证了相等值的稳定性），迭代版则用 head 作头结点、cur 作游标，逐节点把较小者接上 cur.next 并推进游标，最后把剩余非空的那条直接 cur.next = ... 接上。两篇对照可看出"递归省代码、迭代省栈"的取舍：递归版代码最短但递归深度等于链表长度，迭代版用头结点显式管理尾指针、空间 O(1)。

4. 从有序链表中删除重复节点

对应 LeetCode 83. Remove Duplicates from Sorted List（Easy）。

题目要求：链表已排序，删除重复值只保留一个。例如 1->1->2 返回 1->2，1->1->2->3->3 返回 1->2->3。

原文用一段三行的递归完成：先递归处理 head.next 之后的子链表，然后比较 head 与其后继的值——若相等则返回后继（跳过 head），否则返回 head：

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) return head;
    head.next = deleteDuplicates(head.next);
    return head.val == head.next.val ? head.next : head;
}

这里能成立的隐含前提是"链表有序"：相等值必然相邻，因此只需比较当前节点与其直接后继，就能决定是否删除当前节点。head.next = deleteDuplicates(head.next); 一句在递归返回后保证了 head.next 指向的是已去重子链表的头。

5. 删除链表的倒数第 n 个节点

对应 LeetCode 19. Remove Nth Node From End of List（Medium）。

题目示例：1->2->3->4->5，n = 2，删除倒数第二个后得到 1->2->3->5。

核心技巧是快慢双指针。先用 fast 从 head 向前走 n 步，再让 slow 与 fast 同步前进，当 fast 到达尾部（fast.next == null）时，slow 恰好停在"待删除节点的前一个节点"：

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode fast = head;
    while (n-- > 0) {
        fast = fast.next;
    }
    if (fast == null) return head.next;
    ListNode slow = head;
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return head;
}

注意 if (fast == null) return head.next; 这一行专门处理"删除的是头节点"的边界（即 n 等于链表长度时，fast 走完 n 步已越过尾部）。此时慢指针尚未建立，直接返回 head.next 跳过原头节点。

仓库中 剑指 Offer 22. 链表中倒数第 K 个结点 讲的是"找倒数第 K 个结点"（而非删除），用的是同一套快慢指针思想：先让 P1 走 K 步，再让 P2 从 head 出发与 P1 同速前进，当 P1 到尾部时 P2 即停在倒数第 K 个位置。把"定位"换成"定位后断链"就是本题，两题可互相印证双指针间隔控制的正确性。

6. 交换链表中的相邻结点

对应 LeetCode 24. Swap Nodes in Pairs（Medium）。

题目示例：1->2->3->4 应返回 2->1->4->3。约束：不能修改节点的 val 值，空间复杂度 O(1)（即只能交换指针、不能交换数值，也不能用额外数组）。

原文实现用一个头结点统一处理"首对"，pre 作为前驱游标：

public ListNode swapPairs(ListNode head) {
    ListNode node = new ListNode(-1);
    node.next = head;
    ListNode pre = node;
    while (pre.next != null && pre.next.next != null) {
        ListNode l1 = pre.next, l2 = pre.next.next;
        ListNode next = l2.next;
        l1.next = next;
        l2.next = l1;
        pre.next = l2;

        pre = l1;
    }
    return node.next;
}

循环条件 pre.next != null && pre.next.next != null 保证只处理"成对"的节点，落单的尾节点原样保留。每一轮把 pre 之后的两个节点 l1、l2 交换顺序（l2 -> l1），并把交换后的头 l2 接到 pre 上，最后 pre = l1 让游标推进到新对的前驱位置。头结点让首对无需特殊分支即可被统一处理。

7. 链表求和

对应 LeetCode 445. Add Two Numbers II（Medium）。

题目示例：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出 7 -> 8 -> 0 -> 7（即 7243 + 564 = 7807）。约束：不能修改原始链表。

与 LeetCode 2 的"低位在前"不同，本题两个链表都是高位在前，进位必须从最低位（尾部）开始。由于链表不能随机访问，原文采用"先把两条链表的值分别压栈，再从栈顶（低位）开始逐位相加、头插构建结果"的方案：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    Stack<Integer> l1Stack = buildStack(l1);
    Stack<Integer> l2Stack = buildStack(l2);
    ListNode head = new ListNode(-1);
    int carry = 0;
    while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) {
        int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();
        int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();
        int sum = x + y + carry;
        ListNode node = new ListNode(sum % 10);
        node.next = head.next;
        head.next = node;
        carry = sum / 10;
    }
    return head.next;
}

private Stack<Integer> buildStack(ListNode l) {
    Stack<Integer> stack = new Stack<>();
    while (l != null) {
        stack.push(l.val);
        l = l.next;
    }
    return stack;
}

几个细节值得注意：

• 循环条件额外加上 || carry != 0，保证最高位的进位不会丢失（例如 5+5 这类会产生额外一位的情况）。
• sum % 10 取当前位、sum / 10 取进位，是十进制加法的标准拆解。
• 结果用头结点 head 头插构建（node.next = head.next; head.next = node;），因为我们是"从低位向高位"逐位生成新节点，头插恰好能保持最终的高位在前。

这与仓库中 从尾到头打印链表 用栈实现逆序的思路同出一脉——栈的后进先出特性天然适合处理"从尾部开始"的链表问题，本题把栈用在数字上、第 6 题的剑指版本把栈用在节点值上。

8. 回文链表

对应 LeetCode 234. Palindrome Linked List（Easy）。

题目要求 O(1) 空间复杂度。原文思路分三步：切两半、反转后半段、逐位比较。

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    if (fast != null) slow = slow.next;  // 偶数节点，让 slow 指向下一个节点
    cut(head, slow);                     // 切成两个链表
    return isEqual(head, reverse(slow));
}

private void cut(ListNode head, ListNode cutNode) {
    while (head.next != cutNode) {
        head = head.next;
    }
    head.next = null;
}

private ListNode reverse(ListNode head) {
    ListNode newHead = null;
    while (head != null) {
        ListNode nextNode = head.next;
        head.next = newHead;
        newHead = head;
        head = nextNode;
    }
    return newHead;
}

private boolean isEqual(ListNode l1, ListNode l2) {
    while (l1 != null && l2 != null) {
        if (l1.val != l2.val) return false;
        l1 = l1.next;
        l2 = l2.next;
    }
    return true;
}

关键点解析：

• 快慢指针定位中点：slow 每次 +1、fast 每次 +2。注意 fast 初值是 head.next 而非 head，配合后续 if (fast != null) slow = slow.next; 来区分奇偶长度——偶数节点时需要把 slow 再右移一格，使后半段恰好是"后一半"。
• cut 方法把前半段的尾部断开，得到两条独立链表，避免反转时互相干扰。
• reverse 用的是标准的三指针原地反转（与本文第 2 题迭代版同构）。
• isEqual 逐位比较，任一节点不等即返回 false。

需要说明的是，本题在比较时并没有把链表恢复原状（cut 与 reverse 都改变了原结构）。若面试明确要求"不破坏原链表"，可在比较结束后再反转一次并重新拼接；这里以"判定是否为回文"为目标，原文选择了最直接的破坏式实现，空间仍为 O(1)。

仓库中 剑指 Offer 23. 链表中环的入口结点 同样依赖"快指针 +1 次、慢指针 +2 次"的双指针追及模型来证明相遇点，可帮助理解本题快慢指针为何能可靠地找到中点（无环时 fast 先到达尾部）。

9. 分隔链表

对应 LeetCode 725. Split Linked List in Parts（Medium）。

题目描述：把链表分隔成 k 部分，每部分长度尽可能相同，且前面的长度不小于后面的。示例：

Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

即 10 个节点分 3 份，商 3 余 1，所以第一份多一个节点（4 个），其余各 3 个，且"多出来的"必须分给靠前的部分。

原文实现：先遍历一遍数出总长 N，计算每份基准长度 size = N / k 与余数 mod = N % k；然后逐份切分，靠前的 mod 份各多分一个节点（用 mod-- > 0 ? 1 : 0 实现），每切完一份就断开 cur.next：

public ListNode[] splitListToParts(ListNode root, int k) {
    int N = 0;
    ListNode cur = root;
    while (cur != null) {
        N++;
        cur = cur.next;
    }
    int mod = N % k;
    int size = N / k;
    ListNode[] ret = new ListNode[k];
    cur = root;
    for (int i = 0; cur != null && i < k; i++) {
        ret[i] = cur;
        int curSize = size + (mod-- > 0 ? 1 : 0);
        for (int j = 0; j < curSize - 1; j++) {
            cur = cur.next;
        }
        ListNode next = cur.next;
        cur.next = null;
        cur = next;
    }
    return ret;
}

实现要点：

• int curSize = size + (mod-- > 0 ? 1 : 0); 一行同时完成"判断本份是否多一个节点"与"消耗一个余数名额"，保证多出的 mod 个节点被均匀地、且优先分配给靠前的部分，满足"前面不小于后面"的要求。
• for (int j = 0; j < curSize - 1; j++) cur = cur.next; 让 cur 停在"本份最后一个节点"，随后的 cur.next = null 完成断开，cur = next 指向下一份的头。
• 外层 for 同时受 cur != null && i < k 约束：当节点数少于 k 时（比如 N < k），剩余部分自动为空链表（ret[i] 保持 null），不会越界。

10. 链表元素按奇偶聚集

对应 LeetCode 328. Odd Even Linked List（Medium）。

题目示例：1->2->3->4->5->NULL 返回 1->3->5->2->4->NULL。这里"奇偶"指节点位置（第 1、3、5…个为奇位，第 2、4…个为偶位），而非节点值的奇偶。要求把所有奇位节点聚到前面、偶位节点聚到后面，且不改变各自内部的相对顺序。

原文用双链表拼接：odd 走奇位、even 走偶位，各自"跳两格"前进，最后把偶位链表的头接到奇位链表的尾部：

public ListNode oddEvenList(ListNode head) {
    if (head == null) {
        return head;
    }
    ListNode odd = head, even = head.next, evenHead = even;
    while (even != null && even.next != null) {
        odd.next = odd.next.next;
        odd = odd.next;
        even.next = even.next.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;
}

要点：

• evenHead 必须在循环前保存，否则当 even 推进到 null 后，偶位链表的头就丢失了。
• 循环条件 even != null && even.next != null 保证了 odd.next.next 与 even.next.next 的访问安全（跳两格不越界）。
• 每轮 odd、even 各"跨过一个节点"，从而把奇、偶两条子链就地拆开；最后 odd.next = evenHead 把两条子链重新接回，完成聚集。整个过程只改指针、不动节点值，空间 O(1)。

小结：一套指针范式贯穿十题

把这十道题放在一起看，会发现 CS-Notes 这套题解背后的方法高度收敛，可归纳为三条可复用的主线：

1. 递归拆解——"头节点 + 子链表"的自相似结构让反转、归并、去重都能写成几行递归，适合快速理解问题本质（第 2、3、4 题）。
2. 头结点 + 游标——用虚拟头结点统一"首部"与"中间"的操作，避免删除/交换/拼接时丢失链表头，是原地修改类问题的默认工具（第 2、6、7、8 题）。
3. 双指针控制间隔——快慢指针既能定位倒数第 n 个、中点，也能让两个不等长链表"错位对齐"到交点，还能以 O(1) 空间判定回文与找环（第 1、5、8 题）。

这套范式在仓库的 剑指 Offer 题解 系列中还有大量同类变体可对照练习，例如 24. 反转链表、25. 合并两个排序的链表、52. 两个链表的第一个公共结点、22. 链表中倒数第 K 个结点、23. 链表中环的入口结点、6. 从尾到头打印链表。更多 LeetCode 分类题解（树、栈和队列、哈希表、字符串等）的完整索引见 Leetcode 题解 - 目录。