链表基础与核心操作

链表的内存模型

链表和数组是截然不同的数据结构，差异根植于内存布局：

数组（连续）:
1000  1004  1008  1012
[ A  |  B  |  C  |  D ]

链表（分散）:
[ A | 3100 ] → [ B | 0800 ] → [ C | 2400 ] → [ D | null ]
  1000           3100           0800           2400

每个链表节点包含两部分：数据 + 指向下一节点的指针。节点可以散落在内存的任意位置，通过指针串联成逻辑上连续的序列。

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

与数组的对比

虚拟头节点

虚拟头节点（Dummy Node）是链表操作中一个极其重要的技巧，能消除对头节点的特殊处理。

问题：在链表中删除或插入节点时，头节点因为没有前驱节点，往往需要单独讨论。

解法：在链表头部添加一个哑元节点（值任意，通常为 0），让它成为所有真实节点的前驱。

// 删除链表中所有值为 val 的节点
ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode cur = dummy;
    while (cur.next != null) {
        if (cur.next.val == val) {
            cur.next = cur.next.next;  // 跳过目标节点
        } else {
            cur = cur.next;
        }
    }
    return dummy.next;  // 真正的头节点（原头可能被删除了）
}

有了 dummy 之前，删除头节点需要特判：

// 没有 dummy 时的繁琐写法
if (head != null && head.val == val) head = head.next;  // 特判头节点
ListNode cur = head;
// ... 继续处理后续

凡是涉及删除、插入链表节点的题，第一步先建一个 dummy。

双指针技巧

快慢指针：找中间节点

// Floyd 算法：快指针每次走 2 步，慢指针每次走 1 步
// 当快指针到达末尾时，慢指针恰好在中间
ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;  // 偶数长度时，slow 指向后半段的第一个节点
}

列表：1 → 2 → 3 → 4 → 5
         ↑slow      ↑fast  初始：slow=1, fast=1
步骤1：slow=2, fast=3
步骤2：slow=3, fast=5
步骤3：fast.next=null，停止，slow=3 即中间节点 ✓

快慢指针：检测环

// 若链表有环，快慢指针必然在环内相遇
boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;  // 相遇，有环
    }
    return false;  // fast 到达末尾，无环
}

直觉：设想两个人在操场跑步，一个跑得快，一个跑得慢。如果操场是环形的，快的人必然会"套圈"追上慢的人；如果是直道，快的人会先到终点再也不见。

快慢指针：找环的入口

// 在 hasCycle 的基础上，找环的起点
// 关键结论：相遇点到环入口的距离 = 头节点到环入口的距离
ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            // 找到相遇点，让 fast 重回头部，然后同速前进
            fast = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;  // 二次相遇点即为环的入口
        }
    }
    return null;
}

双指针：找倒数第 k 个节点

// 让 fast 先走 k 步，再同速前进，fast 到末尾时 slow 即为目标
ListNode findKthFromEnd(ListNode head, int k) {
    ListNode slow = head, fast = head;
    // fast 先走 k 步
    for (int i = 0; i < k; i++) {
        fast = fast.next;
    }
    // 同步前进
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

链表反转

链表反转是高频基础题，掌握迭代和递归两种写法。

迭代反转（整个链表）

ListNode reverse(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;  // 暂存后继，避免丢失
        cur.next = prev;           // 反转指向
        prev = cur;                // prev 前进
        cur = next;                // cur 前进
    }
    return prev;  // 原链表最后一个节点，即新头节点
}

初始：null ← | 1 → 2 → 3 → null
              ↑prev ↑cur

步骤1：next=2, 1.next=null, prev=1, cur=2
步骤2：next=3, 2.next=1,   prev=2, cur=3
步骤3：next=null, 3.next=2, prev=3, cur=null
返回 prev=3
结果：3 → 2 → 1 → null  ✓

反转部分链表（第 left 到 right 节点）

ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pre = dummy;

    // pre 走到第 left-1 个节点
    for (int i = 1; i < left; i++) pre = pre.next;

    // cur 是待反转部分的第一个节点
    ListNode cur = pre.next;
    for (int i = 0; i < right - left; i++) {
        // "头插法"：把 cur.next 插到 pre 后面
        ListNode next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return dummy.next;
}

合并链表

合并两个有序链表

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), 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;
}

常见坑与注意事项

操作前保存 next 指针

反转或移动节点时，先把 cur.next 存到临时变量，否则修改后就找不到后继了。

不要提前释放节点（Java GC 会处理）

Java 中被解除引用的节点会被垃圾回收，不需要手动 free。但在 C++ 中删除节点时需要 delete。

检查 null

访问 node.next.val 前，确认 node 和 node.next 都不为 null。

// 常见的安全写法
while (cur != null && cur.next != null) {
    // ...
}

小结

链表的核心优势是动态内存分配和 O(1) 的插入/删除（已知前驱时），代价是 O(n) 的随机访问。

三大解题技巧：