1. 输入约定与学习顺序
先读基础知识。普通节点表示为 { val, next },空链表为 null。除环检测外,本文输入都是有限无环单链表;合并的两条链表不能共享节点,且节点值为有限数值。示例函数不负责验证任意外部对象。
数组可以按下标访问,链表必须顺着连接访问。修改连接通常只需常数操作,但找到对应节点可能需要线性时间。先画节点和箭头,再写赋值,避免用“指针移动”掩盖实际修改。
2. 反转:保护尚未处理的后缀
朴素做法可以把节点放进数组,再倒序连接,需要 O(n) 额外空间。原地方法只保存三个引用:已经反转的前缀头、当前节点、旧的下一节点。
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 指向尚未处理的后缀。保存旧 next 后才能改箭头,否则剩余节点可能失联。结束时后缀为空,返回反转后的头。
时间为 O(n),辅助空间为 O(1),会修改原节点连接。空链表返回 null。手推 1 → 2 → 3,每次只画一条被改变的箭头;原来的 head 最终会成为尾节点。
3. 合并有序链表:维护结果尾部
输入两条非降序链表;重复值允许。可以复制所有值后排序,但没有利用已有顺序。直接比较两个头节点,每次连接较小者,剩余部分仍然有序。
function mergeTwoLists(a, b) {
const dummy = { next: null };
let tail = dummy;
while (a !== null && b !== null) {
if (a.val <= b.val) {
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
tail.next = a === null ? b : a;
return dummy.next;
}tail 指向已合并部分的末尾;相等时先取第一条链表的节点,保持各链内部顺序。一条耗尽后,另一条可整体接上。
时间为 O(m + n),辅助空间为 O(1);一个哨兵节点让“插入第一个节点”不需要特殊分支。函数重用并修改节点连接,调用者不能继续把两条旧链当成互相独立的数据。若原数据必须保留,需要明确改成复制节点的版本。
4. 环检测:快慢指针为何会相遇
用集合记录节点身份可以检测重复访问,但需要 O(n) 空间。另一种方法让慢指针每轮一步、快指针每轮两步;若无环,快指针先遇到空引用。若有环,两者进入环后,每轮相对距离改变一步,最终会在环内相遇。
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;
}比较节点引用,不是比较 val。多个节点值相等并不代表有环。时间为 O(n),辅助空间为 O(1),不修改链表。这里 n 是从头可达的不同节点数。
练习:画一个尾节点连回第二个节点的链表;解释为什么相遇节点不一定是入环节点。定位入环点可作为后续变式,本篇先掌握检测。
5. 奇偶链表:按位置拆成两条链
原专题中的奇偶链表保留为进阶练习。奇偶指从 1 开始的位置编号,不是数值奇偶;两个分组内部顺序都应保持。
function oddEvenList(head) {
if (head === null) return null;
let odd = head;
let even = head.next;
const evenHead = even;
while (even !== null && even.next !== null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}把奇数位置接到奇链尾部、偶数位置接到偶链尾部,最后连接奇链尾和偶链头。evenHead 必须单独保留,因为遍历结束时 even 可能已经为空。
时间为 O(n),辅助空间为 O(1);原地修改连接。例如 2 → 1 → 3 → 5 → 6 → 4 → 7 变成 2 → 3 → 6 → 7 → 1 → 5 → 4。
6. 验收与复习
node --test tests/algorithm-structures-examples.test.mjs测试不只比较值,还检查是否保留原节点身份、是否意外成环、合并后是否遗漏节点。覆盖空链、单节点、奇偶长度、重复值、单节点自环和尾部入环。
闭卷完成反转后,再做合并;快慢指针稳定后再做奇偶重排。每道题解释“这次赋值会改变谁看到的连接”,并在至少间隔 3 天后重写。链表操作仍不熟时,不急着写多种递归版本。
评论
正在加载评论…