2.链表

约 999 字大约 3 分钟

2026-04-29

笔记

本文的提到的数组刷题方法、口诀等均由 AI 生成。

刷题口诀：

哑结点，头插不秃头
快慢针，判环找中点
逆置三连：前、当、下，一次遍历掉头娃
合并双序，小者先尾插
断链重组，穿针引线别丢家

哑节点

笔记

核心思路

dummy 是个假头，也就是哑节点，用于返回值。

prev 是前驱指针，是被操作的对象。

适用场景

需要统一处理头节点边界

涉及删除、插入操作时，可以避免对头节点的特殊判断
例如：删除链表中所有值为 val的节点（包括头节点）

需记录前驱节点 (prev)

如：删除倒数第 N 个节点、两两交换节点、反转部分链表等，都需要准确控制 prev指针的位置

题单

模板

ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;   // 前驱指针，想删/插哪里就停哪里

/* --- 下面随题目自由发挥 --- */
// 1. 删除：prev.next = prev.next.next;
// 2. 插入：newNode.next = prev.next; prev.next = newNode;
// 3. 返回：return dummy.next;

快慢指针

题单

模板

// 1) 判环 + 找相遇点（无环返回 null）
ListNode hasCycle(ListNode head) {
    if (head == null) return null;
    ListNode slow = head, fast = head;
    do {                          // 同起点先跑一步
        slow = slow.next;
        fast = fast.next.next;
    } while (fast != null && fast.next != null && slow != fast);
    return (fast == null || fast.next == null) ? null : slow;
}

// 2) 找环入口（调用上面结果）
ListNode detectCycle(ListNode head) {
    ListNode meet = hasCycle(head);
    if (meet == null) return null;
    ListNode slow = head;         // 回表头
    while (slow != meet) {
        slow = slow.next;
        meet = meet.next;
    }
    return slow;                  // 入口下标/节点
}

// 3) 找中点（无环同样适用）
ListNode mid(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;                  // 偶数长度返回后半首
}

逆置三连

题单

模板

ListNode prev = null;          // 已逆区头
ListNode curr = head;          // 当前处理

while (curr != null) {         // 还有节点
    ListNode next = curr.next; // 1. 存后继
    curr.next = prev;          // 2. 掉头
    prev = curr;               // 3. 双指针前挪
    curr = next;
}
return prev;                   // 新头

合并双序

题单

模板

ListNode dummy = new ListNode(0); // 1. 假头
ListNode tail = dummy;            // 2. 尾指针

while (l1 != null && l2 != null) {// 3. 两边都有货
    if (l1.val <= l2.val) {       // 4. 谁小谁上
        tail.next = l1;
        l1 = l1.next;
    } else {
        tail.next = l2;
        l2 = l2.next;
    }
    tail = tail.next;             // 5. 尾巴永远跟最后
}
tail.next = (l1 != null) ? l1 : l2; // 6. 剩的接龙
return dummy.next;

断链重组

题单

模板

// 以经典“分隔链表”为例：把 <x 的放前面，≥x 的放后面
ListNode smallHead = new ListNode(0), bigHead = new ListNode(0);
ListNode smallTail = smallHead, bigTail = bigHead;

for (ListNode curr = head; curr != null; curr = curr.next) {
    if (curr.val < x) {          // 小链尾插
        smallTail.next = curr;
        smallTail = curr;
    } else {                     // 大链尾插
        bigTail.next = curr;
        bigTail = curr;
    }
}
// 拼回家
smallTail.next = bigHead.next;
bigTail.next = null;             // 防环
return smallHead.next;

版权所有

版权归属：FelixJY

许可证：署名-禁止演绎 4.0 国际 (CC-BY-ND-4.0)