算法篇 ｜ 链表

前言

链表是数据结构的基础课题，但在前端面试中，它的出现频率远超你的想象。原因很简单——链表题目代码量不大、边界条件丰富、很考验对指针操作的理解能力，非常适合在 30-45 分钟的面试中考察。

对于前端工程师来说，链表在日常业务中确实不常用（数组才是主角）。但链表题考察的是指针思维和边界处理能力——这种能力在处理 DOM 树操作、虚拟 DOM diff、事件链等场景中是通用的。

链表题有一个好消息和一个坏消息。好消息是：链表题的套路比较固定，掌握几个核心模式就能覆盖大部分题目。坏消息是：链表题对边界条件极其敏感，空指针、头节点、单节点链表这些 edge case 不处理好就容易挂。

本章我们会覆盖：链表基本操作、反转链表、合并有序链表、环检测、删除倒数第 N 个节点，以及链表题中递归思路的运用。

诊断自测

Q1：如何反转一个单链表？要求 O(1) 空间复杂度。

Q2：如何删除链表的倒数第 N 个节点？只遍历一次。

Q3：递归反转链表时，递归函数返回的是什么？递归过程中 head.next.next = head 这行代码是什么意思？

一、链表基础

1.1 节点定义

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

1.2 虚拟头节点（Dummy Node）

链表题中最常用的技巧之一就是虚拟头节点。它解决的核心问题是：当操作可能涉及头节点时，避免对头节点的特殊处理。

// 没有 dummy：删除头节点需要特殊处理
function removeElements(head, val) {
  while (head !== null && head.val === val) {
    head = head.next; // 特殊处理头节点
  }
  let curr = head;
  while (curr !== null && curr.next !== null) {
    if (curr.next.val === val) {
      curr.next = curr.next.next;
    } else {
      curr = curr.next;
    }
  }
  return head;
}

// 有 dummy：统一处理
function removeElements(head, val) {
  const dummy = new ListNode(0, head);
  let curr = dummy;
  while (curr.next !== null) {
    if (curr.next.val === val) {
      curr.next = curr.next.next;
    } else {
      curr = curr.next;
    }
  }
  return dummy.next;
}

什么时候用 dummy？ 当操作可能改变头节点时（删除、插入等），都建议加 dummy。

二、反转链表（LeetCode 206）

反转链表是链表题的”地基”，很多其他题目都以它为基础变体。

2.1 迭代法

function reverseList(head) {
  let prev = null;
  let curr = head;

  while (curr !== null) {
    const next = curr.next; // 先保存下一个节点
    curr.next = prev;       // 反转指向
    prev = curr;            // prev 前进
    curr = next;            // curr 前进
  }

  return prev; // prev 就是新的头节点
}

图解（以 1 → 2 → 3 → null 为例）：

初始状态：  prev=null  curr=1 → 2 → 3 → null
第一步后：  null ← 1   curr=2 → 3 → null   prev=1
第二步后：  null ← 1 ← 2   curr=3 → null   prev=2
第三步后：  null ← 1 ← 2 ← 3   curr=null   prev=3

复杂度：时间 O(n)，空间 O(1)。

2.2 递归法

function reverseList(head) {
  // base case：空链表或只有一个节点
  if (head === null || head.next === null) {
    return head;
  }

  // 递归反转后面的部分
  const newHead = reverseList(head.next);

  // 让后面那个节点指回自己
  head.next.next = head;
  head.next = null; // 断开原来的指向

  return newHead;
}

递归法的关键在于理解 head.next.next = head 这一步。假设链表是 1 → 2 → 3，当递归到 head = 2 时，head.next 是 3，head.next.next = head 就是让 3.next = 2，完成局部反转。

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

2.3 反转链表的前 N 个节点

这是一个很实用的变体，后面”反转链表 II”会用到。

let successor = null; // 第 N+1 个节点

function reverseN(head, n) {
  if (n === 1) {
    successor = head.next; // 记录第 N+1 个节点
    return head;
  }

  const newHead = reverseN(head.next, n - 1);
  head.next.next = head;
  head.next = successor; // 连接到后面未反转的部分

  return newHead;
}

三、合并两个有序链表（LeetCode 21）

将两个升序链表合并为一个新的升序链表。

3.1 迭代法

function mergeTwoLists(list1, list2) {
  const dummy = new ListNode(0);
  let curr = dummy;

  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      curr.next = list1;
      list1 = list1.next;
    } else {
      curr.next = list2;
      list2 = list2.next;
    }
    curr = curr.next;
  }

  // 把剩余的部分直接接上
  curr.next = list1 !== null ? list1 : list2;

  return dummy.next;
}

3.2 递归法

function mergeTwoLists(list1, list2) {
  if (list1 === null) return list2;
  if (list2 === null) return list1;

  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
}

递归写法更简洁，但面试时要注意说明空间复杂度是 O(n)（递归栈）。

复杂度分析：

• 时间复杂度：O(m + n)
• 空间复杂度：迭代法 O(1)，递归法 O(m + n)

四、链表环检测

这部分在双指针那一章已经详细讲过了（Floyd 判圈算法），这里简要回顾并补充一个常见变体。

4.1 判断是否有环（LeetCode 141）

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;
}

4.2 找到环的入口（LeetCode 142）

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

  while (fast !== null && fast.next !== null) {
    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;
}

五、删除链表的倒数第 N 个节点（LeetCode 19）

给定链表，删除倒数第 n 个节点，返回头节点。

核心技巧：快慢指针 + 虚拟头节点。

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

  // 快指针先走 n + 1 步
  for (let i = 0; i <= n; i++) {
    fast = fast.next;
  }

  // 同时走，直到快指针到达末尾
  while (fast !== null) {
    fast = fast.next;
    slow = slow.next;
  }

  // slow 现在指向倒数第 n+1 个节点
  slow.next = slow.next.next;

  return dummy.next;
}

为什么要用 dummy？ 如果要删除的恰好是头节点（比如链表 [1]，删除倒数第 1 个），没有 dummy 的话就需要特殊处理 return head.next。加了 dummy，所有情况统一处理。

为什么快指针先走 n + 1 步而不是 n 步？ 因为我们需要让 slow 停在要删除节点的前一个节点上，才能执行 slow.next = slow.next.next。

复杂度分析：

• 时间复杂度：O(n)，一次遍历
• 空间复杂度：O(1)

六、链表题的递归思路

链表的递归结构和它的物理结构是天然匹配的——每个节点都是一个”当前节点 + 后续子链表”的递归定义。

6.1 递归的三要素

1. base case：通常是 head === null 或 head.next === null
2. 递归调用：对 head.next 递归，处理”后续子链表”
3. 当前层逻辑：在递归返回后，处理当前节点和递归结果的关系

6.2 示例：回文链表（LeetCode 234）

判断一个链表是否为回文链表。

递归思路：利用递归的”回溯”特性，当递归到链表末尾后，从后往前逐个和从前往后的指针比较。

function isPalindrome(head) {
  let front = head;

  function check(node) {
    if (node === null) return true;

    // 先递归到末尾
    const result = check(node.next);

    // 回溯时比较
    if (!result || node.val !== front.val) {
      return false;
    }

    front = front.next;
    return true;
  }

  return check(head);
}

不过这种递归方法空间复杂度是 O(n)。面试中更推荐的 O(1) 空间方法是：快慢指针找中点 → 反转后半部分 → 逐一比较 → （可选）恢复链表。

function isPalindrome(head) {
  if (head === null || head.next === null) return true;

  // 1. 快慢指针找中点
  let slow = head;
  let fast = head;
  while (fast.next !== null && fast.next.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // 2. 反转后半部分
  let secondHalf = reverseList(slow.next);
  let firstHalf = head;

  // 3. 逐一比较
  while (secondHalf !== null) {
    if (firstHalf.val !== secondHalf.val) return false;
    firstHalf = firstHalf.next;
    secondHalf = secondHalf.next;
  }

  return true;
}

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

常见误区

误区一：“链表题不需要虚拟头节点，多写个判断就行了”

虚拟头节点不是偷懒，而是一种消除边界条件的工程实践。手动处理头节点的特殊情况不仅增加代码量，还非常容易出错。面试中时间有限，加一个 dummy 节点能让你少出很多 Bug。

误区二：“递归写法比迭代写法好”

递归写法通常更简洁，但空间复杂度是 O(n)（递归栈），而迭代法通常是 O(1)。面试中两种写法都应该掌握，但如果面试官要求 O(1) 空间，就必须用迭代。另外，递归深度太大时会栈溢出——这在实际工程中是个真实的问题。

误区三：“快慢指针找中点时，慢指针一定停在中间”

对于偶数长度的链表（如 1 → 2 → 3 → 4），慢指针可能停在前半部分的末尾（第 2 个节点）或后半部分的开头（第 3 个节点），取决于循环条件。while (fast.next && fast.next.next) 会让 slow 停在前半部分末尾，while (fast && fast.next) 会让 slow 停在后半部分开头。做题时要根据需要选择正确的条件。

误区四：“链表题的 edge case 不重要”

链表题最容易挂的地方就是 edge case：空链表、单节点链表、两个节点的链表、删除头节点、删除尾节点。写完代码后，一定要用这些 case 走一遍。面试官也经常会在你写完后问”如果链表为空呢？如果只有一个节点呢？“

小结

链表题虽然代码量不大，但对指针操作和边界处理的要求很高。本章我们覆盖了链表面试中最核心的几类题目。

核心要点

1. 虚拟头节点（Dummy）：统一处理头节点的边界情况，强烈建议在链表题中默认使用
2. 反转链表：迭代法用三个指针（prev/curr/next），递归法理解”局部反转”
3. 合并有序链表：迭代或递归，注意处理剩余部分
4. 环检测：Floyd 判圈算法（快慢指针），找环入口需要数学推导
5. 删除倒数第 N 个：快慢指针 + dummy，快指针先走 n+1 步
6. 递归思路：链表的递归结构天然适合递归解法，但要注意空间复杂度

链表题的做题策略

1. 先确认是否需要 dummy 节点
2. 画图理清指针的变化过程
3. 先写出正确的逻辑，再优化
4. 写完后用空链表、单节点、两个节点测试

本章思维导图

练习挑战

第一题 ⭐：反转链表（LeetCode 206）

反转一个单链表。

// 示例
// 输入: 1 → 2 → 3 → 4 → 5 → null
// 输出: 5 → 4 → 3 → 2 → 1 → null

// 迭代法
function reverseList(head) {
  let prev = null;
  let curr = head;

  while (curr !== null) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  return prev;
}

第二题 ⭐⭐：两数相加（LeetCode 2）

给定两个非空链表，表示两个非负整数（逆序存储），求它们的和，结果同样用链表表示。

// 示例
// 输入: (2 → 4 → 3) + (5 → 6 → 4)
// 输出: 7 → 0 → 8（因为 342 + 465 = 807）

function addTwoNumbers(l1, l2) {
  const dummy = new ListNode(0);
  let curr = dummy;
  let carry = 0;

  while (l1 !== null || l2 !== null || carry > 0) {
    const sum = (l1?.val || 0) + (l2?.val || 0) + carry;
    carry = Math.floor(sum / 10);
    curr.next = new ListNode(sum % 10);
    curr = curr.next;

    if (l1) l1 = l1.next;
    if (l2) l2 = l2.next;
  }

  return dummy.next;
}

第三题 ⭐⭐⭐：K 个一组翻转链表（LeetCode 25）

给定一个链表，每 k 个节点一组进行翻转，返回翻转后的链表。如果最后不足 k 个节点则保持原样。

function reverseKGroup(head, k) {
  const dummy = new ListNode(0, head);
  let prevGroup = dummy;

  while (true) {
    // 检查剩余节点是否 >= k
    let check = prevGroup;
    for (let i = 0; i < k; i++) {
      check = check.next;
      if (check === null) return dummy.next; // 不足 k 个，直接返回
    }

    // 反转 k 个节点
    let prev = null;
    let curr = prevGroup.next;
    for (let i = 0; i < k; i++) {
      const next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }

    // 连接：prevGroup → 反转后的头(prev)，反转后的尾(原来的头) → curr
    const tail = prevGroup.next; // 反转后变成了尾巴
    tail.next = curr;
    prevGroup.next = prev;

    // 移动 prevGroup 到下一组的前一个位置
    prevGroup = tail;
  }
}

自我检测

• 能默写反转链表的迭代法（三指针），并在纸上画出指针变化过程
• 能用递归法反转链表，并解释 head.next.next = head 的含义
• 知道什么时候该用虚拟头节点，以及为什么它能简化边界处理
• 能用迭代法合并两个有序链表
• 能用快慢指针判断链表是否有环，并找到环的入口
• 能用快慢指针 + dummy 节点删除链表的倒数第 N 个节点
• 能说出链表题中常见的 edge case（空链表、单节点、头节点操作）
• 能根据题目需求选择迭代或递归，并分析各自的时空复杂度