链表方法论与面试进阶

链表题的核心不是记住代码，而是在修改指针前保存仍需访问的节点，并明确每一步之后链表保持什么结构。

链表特征

链表由节点通过引用连接，节点在内存中不要求连续。

• 访问第 i 个节点需要从头遍历，时间复杂度为 O(n)。
• 已知目标节点或前驱节点时，插入和删除可以达到 O(1)。
• 数组随机访问快、缓存局部性好；链表更适合频繁连接和拆分节点的场景。

class ListNode {
  constructor(value, next = null) {
    this.value = value
    this.next = next
  }
}

常见类型包括单向链表、双向链表和循环链表。算法题中通常使用单向链表。

遍历模板

function toArray(head) {
  const values = []
  let current = head

  while (current !== null) {
    values.push(current.value)
    current = current.next
  }

  return values
}

循环开始前和每轮结束后，current 都表示“下一个尚未处理的节点”。明确这种循环不变量可以减少空指针和漏节点错误。

哨兵节点

当头节点也可能被删除或插入时，创建一个虚拟头节点可以统一边界逻辑。

function removeValue(head, target) {
  const dummy = new ListNode(0, head)
  let previous = dummy

  while (previous.next !== null) {
    if (previous.next.value === target) {
      previous.next = previous.next.next
    } else {
      previous = previous.next
    }
  }

  return dummy.next
}

这里始终检查 previous.next，因此删除真实头节点与删除中间节点使用同一段逻辑。

反转链表

修改 current.next 前，必须先保存原来的下一个节点，否则剩余链表会丢失。

function reverseList(head) {
  let previous = null
  let current = head

  while (current !== null) {
    const next = current.next
    current.next = previous
    previous = current
    current = next
  }

  return previous
}

循环不变量：previous 是已经反转完成的链表头，current 是尚未处理部分的头。

时间复杂度为 O(n)，额外空间为 O(1)。

合并两个有序链表

function mergeSortedLists(first, second) {
  const dummy = new ListNode(0)
  let tail = dummy

  while (first !== null && second !== null) {
    if (first.value <= second.value) {
      tail.next = first
      first = first.next
    } else {
      tail.next = second
      second = second.next
    }

    tail = tail.next
  }

  tail.next = first ?? second
  return dummy.next
}

tail 始终指向结果链表的最后一个节点。循环结束后，未处理链表已经有序，可以整体连接。

快慢指针找中点

快指针每次走两步，慢指针每次走一步。快指针到达末尾时，慢指针位于中点。

function middleNode(head) {
  let slow = head
  let fast = head

  while (fast !== null && fast.next !== null) {
    slow = slow.next
    fast = fast.next.next
  }

  return slow
}

偶数长度链表中，这个实现返回两个中间节点中的后一个。若题目要求前一个中点，需要调整初始位置或循环条件。

判断环

如果存在环，快慢指针最终会在环内相遇；如果不存在环，快指针会先到达 null。

function hasCycle(head) {
  let slow = head
  let fast = head

  while (fast !== null && fast.next !== null) {
    slow = slow.next
    fast = fast.next.next

    if (slow === fast) return true
  }

  return false
}

这里比较的是节点引用，而不是节点值。不同节点可以拥有相同值。

删除倒数第 N 个节点

让快指针先走 n 步，再让快慢指针同步移动。快指针到达末尾时，慢指针位于目标节点的前驱。

function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head)
  let slow = dummy
  let fast = dummy

  for (let step = 0; step < n; step += 1) {
    fast = fast.next
  }

  while (fast.next !== null) {
    slow = slow.next
    fast = fast.next
  }

  slow.next = slow.next.next
  return dummy.next
}

生产代码还应定义 n 超出链表长度时的行为，例如抛错或原样返回。

指针题的统一分析方法

写代码前先为每个指针写一句职责，并说明循环开始时的结构不变量。常见角色包括：

• current：下一个尚未处理的节点。
• previous：已处理部分的尾或目标节点前驱。
• tail：结果链表最后一个有效节点。
• fast/slow：维持固定距离或速度比例。
• dummy：稳定表示真实头节点之前的位置。

每次重连按“先保存出口，再修改箭头，最后移动指针”的顺序：

const next = current.next
current.next = previous
previous = current
current = next

如果同时修改多个链接，先画出修改前后的局部图，标记哪些节点仍只能通过即将覆盖的指针访问。链表题的大部分 bug 是丢失可达性，而不是语法问题。

还要明确函数契约：是否允许原地修改；节点身份是否有意义；输入是否保证无环；失败时抛错还是返回特殊值。不同契约会改变最优方案。

找到环的入口

Floyd 算法第一次相遇后，把一个指针移回头节点，两者每次都走一步，再次相遇的位置就是环入口：

function detectCycle(head) {
  let slow = head
  let fast = head

  do {
    if (fast === null || fast.next === null) return null
    slow = slow.next
    fast = fast.next.next
  } while (slow !== fast)

  slow = head

  while (slow !== fast) {
    slow = slow.next
    fast = fast.next
  }

  return slow
}

设头到入口距离为 a，入口到首次相遇点为 b，环长为 c。相遇时慢指针走了 a + b，快指针比它多走若干整环，因此 2(a + b) = a + b + kc，得到 a = kc - b。从头走 a 与从相遇点继续走 kc - b 会同时到入口。

这种解释比背“相遇后一个回头”更重要，因为面试官可能继续问速度不是 2 倍、如何求环长、为何必然相遇。

相交链表

两个无环单链表若相交，从交点开始共享同一节点引用与后缀。双指针分别走完自己的链表后切换到另一条头部，可以抵消长度差：

function getIntersectionNode(first, second) {
  let left = first
  let right = second

  while (left !== right) {
    left = left === null ? second : left.next
    right = right === null ? first : right.next
  }

  return left
}

若前缀长度分别为 a、b，共享后缀为 c，两个指针最多都走 a + b + c 后对齐。无交点时最终都为 null。比较必须使用节点引用，不能比较值。

若输入可能有环，问题要先分类：两条都无环；一条有环一条无环；两条有环且入口相同；两条环入口不同但处在同一环。不能直接套无环算法。

反转指定区间

反转 [left, right] 时，哨兵节点让 left = 1 与普通位置一致。头插法每轮把区间内下一个节点移动到区间头部：

function reverseBetween(head, left, right) {
  if (left === right) return head

  const dummy = new ListNode(0, head)
  let before = dummy

  for (let index = 1; index < left; index += 1) {
    before = before.next
  }

  const tail = before.next

  for (let index = 0; index < right - left; index += 1) {
    const moved = tail.next
    tail.next = moved.next
    moved.next = before.next
    before.next = moved
  }

  return dummy.next
}

循环不变量：before.next 是已反转区间头，tail 是已反转区间尾，tail.next 是下一个待移动节点。每轮同时维持区间前、区间内部和区间后的连通性。

如果题目保证位置合法，上述代码足够；生产函数应验证 left/right、空链表和长度，避免访问 null.next。

K 个一组反转

K 组反转可以拆成三个独立问题：

1. 从当前组前驱向后探测 k 个节点，不足 k 个则保持原样。
2. 在半开区间 [groupStart, groupNext) 内反转。
3. 把上一段尾、反转后的组和剩余段重新连接。

function reverseKGroup(head, k) {
  if (k <= 1) return head

  const dummy = new ListNode(0, head)
  let groupPrevious = dummy

  while (true) {
    let kth = groupPrevious

    for (let step = 0; step < k && kth !== null; step += 1) {
      kth = kth.next
    }

    if (kth === null) break

    const groupNext = kth.next
    let previous = groupNext
    let current = groupPrevious.next

    while (current !== groupNext) {
      const next = current.next
      current.next = previous
      previous = current
      current = next
    }

    const oldGroupStart = groupPrevious.next
    groupPrevious.next = kth
    groupPrevious = oldGroupStart
  }

  return dummy.next
}

时间复杂度 O(n)，每个节点参与常数次操作；额外空间 O(1)。面试时先说明不足一组为何不能修改，再写探测逻辑，能显著减少边界错误。

回文链表与输入恢复

O(1) 额外空间判断回文的常见方法是：快慢指针找到中点，反转后半段，逐节点比较。工程代码应在返回前把后半段再反转回来，恢复调用方传入的结构，除非契约明确允许修改。

恢复不是渐进复杂度要求，却体现 API 意识。面试中主动说明“算法原地修改了输入，若调用方仍需使用则恢复”通常比只报 O(1) 更完整。

对奇数长度，中点节点无需参与成对比较；对偶数长度，要明确 slow 最终指向后半段第一个节点还是前半段最后一个节点，并让反转起点与循环条件保持一致。

链表排序

归并排序适合链表：找中点可 O(n)，合并有序链表可复用节点且不需要随机访问。递归版本满足：

T(n) = 2T(n / 2) + O(n) = O(n log n)

额外空间按递归栈计算为 O(log n)；自底向上的迭代归并可达到 O(1) 额外辅助空间。快速排序在链表上难以发挥数组的原地分区和缓存局部性优势，通常不是首选。

面试中若声称“链表归并空间 O(1)”，必须说明采用迭代版本；普通递归实现不能忽略调用栈。

双向链表与 LRU Cache

LRU Cache 需要 get/put 平均 O(1)：Map 按 key 找节点，双向链表按最近使用顺序排列。访问节点时把它移动到头部；容量满时从尾部淘汰。

为什么是双向链表：Map 只能直接得到目标节点；删除该节点还需要其前驱。单链表无法仅凭节点在 O(1) 找到前驱，双向节点可直接重连 previous/next。

工程实现还要明确：

• 更新已有 key 是否计为最近使用。
• 容量为 0 的行为。
• 缓存值大小差异是否需要按权重淘汰，而不是只按条数。
• TTL 与 LRU 同时存在时，过期清理策略是什么。
• JavaScript Map 本身保持插入顺序，简单场景可通过删后重插实现 LRU，但频繁操作、容量和语义仍应评估。

复杂度与数据局部性

“链表插入删除是 O(1)”有前提：已经持有目标位置和所需前驱。如果先按值查找，整体仍是 O(n)。双向链表已知节点时删除是 O(1)，单链表只持有当前节点时通常缺少前驱。

数组即使中间插入是 O(n)，连续内存和缓存局部性让实际遍历远快于对象节点链。JavaScript 对象节点还有 GC 与引用开销。生产选型要结合访问模式、数据规模和引擎实现，不以大 O 单独决定。

面试走查模板

1. 复述节点结构、空值、是否有环和能否修改输入。
2. 画出至少三个节点和所有指针角色。
3. 说明循环不变量与停止条件。
4. 每次覆盖 next 前指出剩余链表从哪里可达。
5. 用空、单节点、双节点、奇偶长度和边界位置走查。
6. 报告时间、辅助空间和是否恢复输入。

代码完成后不要只用值序列验证。重复值链表可以暴露错误的值比较；保存节点对象并检查引用关系，才能验证是否真正复用了、删除了或相交于正确节点。

资深面试追问

如何在 O(1) 删除只给定的节点？

若它不是尾节点，可把后继节点的值复制到当前节点，再跳过后继。实际上删除的是后继节点并改变了当前节点的值与语义；若外部持有节点引用、值不可复制或目标是尾节点，就不成立。回答必须说明这些限制。（深入阅读：链表操作的前提）

快慢指针为什么能找到中点？

每轮 fast 走两步、slow 走一步。fast 走过约 n 个节点停止时，slow 走过约 n/2。具体返回前中点还是后中点由初值和循环条件决定，必须结合题目对偶数长度的定义。（深入阅读：快慢指针找中点）

如何复制带随机指针的链表？

通用方案用 Map 建立旧节点到新节点映射，两轮分别创建节点和连接 next/random，时间 O(n)、空间 O(n)。若允许修改输入，可把新节点交织到旧节点后，利用相邻关系设置 random，再拆分，达到 O(1) 辅助空间；过程中必须最终恢复原链表。（深入阅读：指针题的统一分析方法）

链表和数组如何选？

数组适合随机访问、紧凑存储和高频遍历；链表适合持有节点引用后的连接、拆分和稳定节点身份。真实系统还要考虑语言内存模型、GC、缓存局部性和 API 需求。不能只用“增删快、查询慢”概括。（深入阅读：复杂度与数据局部性）

常见错误

• 重连指针前没有保存 next，导致后续节点丢失。
• 删除头节点时忘记更新返回值。
• 在循环条件中访问 fast.next 前没有确认 fast 非空。
• 用节点值判断是否为同一节点。
• 反转局部链表后没有重新连接前后两段。
• 忽略空链表、单节点、双节点和存在环的输入。

调试方法

1. 画出节点和箭头，不只写值序列。
2. 每次只修改一个 next，记录修改前后的指向。
3. 用 null、单节点、双节点和普通链表逐一走查。
4. 明确函数是否允许修改输入链表。
5. 必要时设置最大遍历次数，防止调试环形链表时无限循环。

解题检查

• 函数对空链表有明确结果。
• 头节点变化时使用哨兵或显式更新返回值。
• 所有被覆盖的指针都已提前保存。
• 循环条件不会访问空节点属性。
• 时间、额外空间和是否原地修改都已说明。
• 测试覆盖空、单节点、偶数、奇数、重复值和环等边界。
• 每个指针都有稳定职责，并能陈述循环不变量。
• 局部反转后正确连接前缀、反转段和后缀。
• 若输入结构仍被调用方使用，算法会恢复或明确声明修改行为。