Skip to content

链表深入

实现单链表、双链表和循环链表;掌握指针操作和环检测。

你将学到

  • 单链表、双链表和循环链表变体
  • 指针操作:插入、删除、反转
  • Floyd 环检测算法
  • 链表上的归并排序

概念讲解

链表深入

链表将元素存储在节点中,每个指向下一个。与数组不同,链表不连续存储元素,因此在已知位置插入删除为 O(1)——只需重新链接指针。代价是 O(n) 随机访问。

变体

单链表:每个节点有 next 指针,单向遍历。双链表:每个节点有 next 和 prev,允许反向遍历和给定节点引用的 O(1) 删除。循环链表:最后节点指回头节点,适用于轮转调度。

指针操作

关键技巧是画出操作前后的指针。在 A 后插入 B:B.next = A.next; A.next = B。顺序很重要——如果先设 A.next = B,就丢失了原 next 的引用。反转链表时,维护三个指针并在每步重新链接。

环检测

Floyd 算法使用两个指针:慢指针(1 步)和快指针(2 步)。如果有环,它们会相遇。如果快指针到达 null,则无环。这使用 O(1) 空间。

链表上的归并排序

归并排序是链表的自然排序算法:在中点分割,递归排序每半,然后合并。它是 O(n log n) 且 O(1) 额外空间。

示例代码

              class Node { constructor(val) { this.val = val; this.next = null; } }
function fromArray(arr) {
  const dummy = new Node(0); let tail = dummy;
  for (const v of arr) { tail.next = new Node(v); tail = tail.next; }
  return dummy.next;
}
function reverse(head) {
  let prev = null, curr = head;
  while (curr) { const next = curr.next; curr.next = prev; prev = curr; curr = next; }
  return prev;
}
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next; fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}
function toArray(head) { const r = []; let c = head; while (c) { r.push(c.val); c = c.next; } return r; }
const list = fromArray([1, 2, 3, 4, 5]);
console.log('Original:', toArray(list));
console.log('Reversed:', toArray(reverse(list)));
            

reverse 用三个指针遍历链表,将每个 next 翻转为向后指。hasCycle 使用 Floyd 龟兔赛跑:如果它们相遇,则存在环。

动手试一试

  • JSON Formatter

    链表序列化为 JSON 数组——观察链式和连续存储的结构差异。

常见错误

错误写法

在保存指针之前断开而丢失链表剩余部分。

正确做法

覆盖前总是保存 next 指针。temp = curr.next; curr.next = newNext。

错误写法

忘记处理边界情况:空链表、单节点、两节点。

正确做法

空链表的反转为空。单节点的反转为自身。明确测试这些。

查阅不认识的术语

新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。

查看术语表

动手做项目

通过引导式项目应用所学,含起始代码与解决方案。

查看项目

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误