链表深入
实现单链表、双链表和循环链表;掌握指针操作和环检测。
你将学到
- 单链表、双链表和循环链表变体
- 指针操作:插入、删除、反转
- 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 等等。
动手做项目
通过引导式项目应用所学,含起始代码与解决方案。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。