链表

介绍

链表，一个节点指向下一个节点。遍历靠 node = node.next 一步步走。在算法题中，链表也是树形结构的基础。

一句话直觉：链表题 = 玩指针。核心就三个工具：dummy node（统一边界）、快慢指针（找位置）、画图追踪（别在脑子里模拟）。

ArrayList vs LinkedList — 必考题

这可能是 Java 面试中最常问的数据结构对比：

	ArrayList	LinkedList
底层	动态数组	双向链表
随机访问 get(i)	O(1)	O(n)
头/尾插入删除	O(n) 头 / O(1) 尾	O(1)
内存	连续内存，cache 友好	每个节点有 prev/next 指针开销
适用	随机访问多，尾部追加	频繁头/中间插入删除

判断原则：绝大多数场景用 ArrayList（cache 友好 + O(1) 随机访问）。LinkedList 只在频繁在头部插入删除时才考虑。

// Definition for singly-linked list
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

模式识别

当你看到这些信号：

• “原地修改”、“O(1) 空间”、“不能新建链表” → 操作指针，别复制值
• “找中点”、“找倒数第 n 个”、“检测环” → 快慢指针
• “删除/插入头节点可能不同” → 哑节点 (Dummy Node)
• “合并”、“反转” → 画图追踪指针，别在脑子里模拟

核心模式

遍历条件

遍历链表时有三种常见循环条件，选错会导致 NPE 或漏掉最后一个节点：

条件	停止位置	使用场景
while (node != null)	停在最后一个节点 +1 (null)	只用当前节点的值
while (node.next != null)	停在最后一个节点	需要访问下一个节点的值
node = node.next	—	前进一步

哑节点 (Dummy Node)

在链表头前加一个虚拟节点，统一处理边界（头节点被删除、空链表等场景）。几乎所有链表题都能用 dummy node 简化代码。

快慢指针 (Fast & Slow Pointers)

• 找中点：快指针每次走两步，慢指针走一步。快指针到末尾时，慢指针恰好在中间
• 找倒数第 n 个：快指针先走 n 步，然后两个指针同步走；快指针到底时，慢指针指向倒数第 n+1 个

代码挑战

1. Remove Nth Node From End

问题：删除链表倒数第 n 个节点，返回头节点。

思路：快慢指针。快指针先走 n 步，然后同步走到底。慢指针停在倒数第 n+1 位，直接删除下一个节点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;

    // move fast n steps ahead
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }

    // move both until fast reaches the last node
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }

    // delete the nth node from end
    slow.next = slow.next.next;

    return dummy.next;
}

2. Merge Two Sorted Lists

问题：合并两个有序链表，返回新的有序链表。

迭代解法：用 dummy node 统一边界，逐一比较两个链表的当前节点，接到结果链表上。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }

    // attach remaining nodes
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.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;
    }
}

关键技巧

• Dummy node 是链表题的万能钥匙 — 避免处理头节点被删的特殊情况
• 比较两个链表时注意三种情况：null、l1 > l2、l1 < l2
• 快慢指针两招：找中点（fast 两步 slow 一步），找倒数第 n 个（fast 先行 n 步）
• 链表天然适合递归 — 每个节点本身就是一个”更小的链表”

参考资料

• LeetCode — Remove Nth Node From End of List
• LeetCode — Merge Two Sorted Lists