题库/手写题/题目详解
宝典补充约 5 分钟阅读

手写链表的反转、合并两个有序链表和查找中间节点。

先理解原理和示例，再练习完整口述与追问。

回答要点

反转用 prev、cur 两个指针逐个调转 next，先保存后继；合并用哨兵节点 dummy 简化头节点处理，比较两表头较小者接到尾部，最后接上剩余部分；中间节点用快慢指针，快指针每次两步、慢指针一步，偶数长度时返回第二个中间节点。均为 O(n) 时间、O(1) 额外空间。

原理拆解

链表题的关键是修改指针前先保存会丢失的引用。反转时如果先写 cur.next = prev，就失去了原来的后继，所以先 const next = cur.next。哨兵节点让“结果链表为空”和“非空”走同一套逻辑，最后返回 dummy.next。快慢指针循环条件 fast && fast.next，保证 fast.next.next 不会访问 null 的属性；快指针到达末尾时慢指针正好在中间。同样的方法还能判断链表是否有环（快慢指针相遇）。

示例与推演

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

function fromArray(values) {
  const dummy = new ListNode(0)
  let tail = dummy
  for (const value of values) tail = tail.next = new ListNode(value)
  return dummy.next
}

function toArray(head) {
  const values = []
  for (let node = head; node; node = node.next) values.push(node.val)
  return values
}

function reverseList(head) {
  let prev = null
  let cur = head
  while (cur) {
    const next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev
}

function mergeTwoLists(a, b) {
  const dummy = new ListNode(0)
  let tail = dummy
  while (a && b) {
    if (a.val <= b.val) {
      tail.next = a
      a = a.next
    } else {
      tail.next = b
      b = b.next
    }
    tail = tail.next
  }
  tail.next = a || b
  return dummy.next
}

function middleNode(head) {
  let slow = head
  let fast = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
  }
  return slow
}

推演：[1, 2, 3, 4] 中，快指针依次在 1、3、末尾之后，慢指针依次在 1、2、3，返回值为 3 的节点，即第二个中间节点；mergeTwoLists 中相等时取 a 的节点，保持稳定。

易错点

反转后忘记原头节点的 next 变为 null 会导致成环（上面的写法第一次迭代即设为 null）；合并时遗漏剩余部分；空链表输入未处理。

参考回答可直接练习口述

反转链表用 prev 和 cur 两个指针，每一步先保存 cur.next，再把 cur 指向 prev，然后两个指针前移，最后 prev 就是新头。合并两个有序链表用哨兵节点，每次把较小的节点接到尾部，循环结束后把剩余的那条直接接上，返回 dummy.next。中间节点用快慢指针，快的走两步慢的走一步，快的到末尾时慢的就在中间，偶数长度返回第二个。