代码随想录 — 链表

对应 leetcode-master：链表理论基础、203/707/206/24/19、相交、142 环形链表 等。

---

一、链表理论基础（有助于理解为什么这样写）

• 定义：通过指针串联的线性结构；每个节点包含数据域和指针域（指向下一节点），最后一个节点指向 null。
• 类型：单链表、双链表（可前可后查）、循环链表（首尾相连）。
• 存储：节点在内存中不必连续，靠指针链接；增删只改指针，不移动其它节点，所以单次插入/删除为 O(1)，但按位置访问需要遍历，为 O(n)。
• 与数组对比：数组连续、定长（或需扩容），适合查多改少；链表非连续、长度可变，适合改多查少。

面试注意：很多题默认给好了节点类，但要知道节点怎么定义（值 + next）；手写链表时构造函数要会写，避免未初始化。

---

二、移除链表元素（203）

题意：删除链表中所有值等于 val 的节点。

思路：虚拟头结点可以统一「删头」和「删中间」的逻辑。用 dummy.next = head，然后 cur 从 dummy 开始，若 cur.next.val === val 则 cur.next = cur.next.next，否则 cur = cur.next。最后返回 dummy.next。这样头结点若要删也会被自然跳过，无需单独判断。

---

三、设计链表（707）

题意：实现单链表的 get、addAtHead、addAtTail、addAtIndex、deleteAtIndex。

思路：维护一个带虚拟头结点的单链表和 size。在指定下标插入/删除时，先走到前驱节点（index 步或 index-1 步），再改指针。注意 index 的合法性（0～size）；头插可复用 addAtIndex(0, val)，尾插 addAtIndex(size, val)。

---

四、反转链表（206）— 重点

题意：反转单链表。

思路一（推荐）：双指针迭代

• 不新建链表，只改 next 指向。设 pre = null，cur = head。
• 每次先用 temp 保存 cur.next，然后 cur.next = pre，再 pre = cur，cur = temp。
• 当 cur 为 null 时结束，此时 pre 为新头结点。

要点：一定要先保存 cur.next，否则改完 cur.next 就找不到原来的下一节点了。

思路二：递归（从前往后）

• 写一个函数 reverse(pre, cur)：若 cur 为空返回 pre；否则保存 cur.next，把 cur.next 改为 pre，然后 return reverse(cur, temp)。
• 入口：return reverse(null, head)。逻辑和双指针一致，只是用递归代替循环。

思路三：递归（从后往前）

• 先递归到最后一个节点，返回为 newHead；在回溯时把「当前节点的下一个节点的 next」指向当前节点，再把当前节点 next 置空。理解难度略大，掌握一种递归写法即可。

复杂度：时间 O(n)，迭代空间 O(1)，递归空间 O(n)（栈深度）。

---

五、两两交换链表中的节点（24）

题意：两两交换相邻节点，只改指针，不改值。

思路：虚拟头结点 + 三个指针。设 dummy，pre 指向「当前要交换的一对」的前一个节点，cur 和 next 为这一对。交换步骤：pre.next = next，cur.next = next.next，next.next = cur；然后 pre = cur，继续下一对。画图理清指针顺序，避免断链。

---

六、删除链表的倒数第 N 个结点（19）

题意：删除倒数第 n 个节点，返回头结点。

思路：快慢指针。快指针先走 n 步（或 n+1 步，取决于要删的是「当前慢指针的下一个」还是「慢指针本身」）。若用虚拟头结点，让 slow 指向「待删节点的前驱」更统一：快慢都从 dummy 开始，快先走 n+1 步，然后快慢一起走，快到 null 时，slow.next 即为待删节点，执行 slow.next = slow.next.next。

---

七、链表相交（面试题 02.07）

题意：两链表可能在某节点后重合，求第一个公共节点，无则返回 null。

思路：若允许 O(n) 空间，可用 Set 存一条链的节点再遍历另一条。O(1) 空间：把两条链都走完，指针 A 走完 listA 后从 listB 头再走，指针 B 走完 listB 后从 listA 头再走；这样两指针路程相同，若有交点会在交点相遇，若无交点会同时到 null。

---

八、环形链表 II（142）

题意：判断是否有环，若有，返回环的入口节点。

思路：快慢指针。快每次走 2 步，慢走 1 步；若相遇则一定有环。相遇后，把其中一个放回 head，两指针都改为每次走 1 步，再次相遇的节点即为环入口（可用公式推导：相遇点到入口的距离 = head 到入口的距离）。若快指针先到 null 则无环。

---

九、链表总结

技巧	适用
虚拟头结点	统一头结点可能被删/被改的逻辑（203、707、24 等）
双指针迭代	反转、找倒数第 k 个、快慢判环
先保存 next	反转、交换节点时防止断链
相交/环	数学关系：路程差、环长与入口关系

建议：206 反转链表必须非常熟（双指针 + 递归各一遍）；203、19、142 也是高频题，要能讲清「为什么这样写」。

---

附：核心代码模板

链表节点定义

// JavaScript
class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

反转链表（双指针迭代）

// JavaScript — 时间 O(n)，空间 O(1)
function reverseList(head) {
  let pre = null, cur = head;
  while (cur) {
    const temp = cur.next;
    cur.next = pre;
    pre = cur;
    cur = temp;
  }
  return pre;
}

# Python
def reverse_list(head):
    pre, cur = None, head
    while cur:
        temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    return pre

虚拟头结点 — 移除链表元素

// JavaScript
function removeElements(head, val) {
  const dummy = new ListNode(0, head);
  let cur = dummy;
  while (cur.next) {
    if (cur.next.val === val) {
      cur.next = cur.next.next;
    } else {
      cur = cur.next;
    }
  }
  return dummy.next;
}

快慢指针 — 环形链表入口

// JavaScript — 时间 O(n)，空间 O(1)
function detectCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      let ptr = head;
      while (ptr !== slow) {
        ptr = ptr.next;
        slow = slow.next;
      }
      return ptr;
    }
  }
  return null;
}