一、手撕链表：程序员的必修课
链表是数据结构中最基础也最常考的类型，就像学吉他必练《小星星》一样。工作中虽然有很多现成的库可以用，但能手写链表操作才是真本事。今天咱们就用JavaScript这个技术栈，来聊聊反转链表、判断环形链表、合并有序链表这三个经典题目。
先看个简单的链表节点定义：
// JavaScript链表节点定义
class ListNode {
constructor(val, next = null) {
this.val = val; // 节点值
this.next = next; // 指向下一个节点的指针
}
}
二、反转链表：指针的华尔兹
反转链表就像把一串珍珠项链重新穿线，需要小心翼翼地调整每个节点的指向。最常见的解法是用三个指针跳"指针华尔兹"。
来看具体实现：
function reverseList(head) {
let prev = null; // 前驱节点，初始为null
let curr = head; // 当前节点，从头节点开始
while (curr !== null) {
const next = curr.next; // 临时保存下一个节点
curr.next = prev; // 反转指针方向
prev = curr; // 前驱节点前进
curr = next; // 当前节点前进
}
return prev; // 最后prev就是新的头节点
}
// 示例：1->2->3->null
const head = new ListNode(1, new ListNode(2, new ListNode(3)));
console.log(reverseList(head)); // 输出：3->2->1->null
应用场景：浏览器历史记录的回退功能、文本编辑器的撤销操作等都需要类似的反向遍历能力。
注意事项：
- 边界处理：空链表直接返回null
- 不要丢失节点引用：一定要先用临时变量保存next节点
- 时间复杂度O(n)，空间复杂度O(1)，已经是最优解
三、环形链表判断：快慢指针的龟兔赛跑
判断链表是否有环，就像检查操场跑步有没有人超圈。最优雅的解法是Floyd判圈算法，用快慢指针就像龟兔赛跑。
来看代码实现：
function hasCycle(head) {
if (!head || !head.next) return false; // 空链表或单节点无环
let slow = head; // 乌龟每次走一步
let fast = head.next; // 兔子每次走两步
while (slow !== fast) {
if (!fast || !fast.next) return false; // 兔子跑到终点
slow = slow.next; // 乌龟走一步
fast = fast.next.next; // 兔子走两步
}
return true; // 龟兔相遇说明有环
}
// 示例：创建带环链表 1->2->3->4->2
const node1 = new ListNode(1);
const node2 = new ListNode(2);
node1.next = node2;
node2.next = new ListNode(3, new ListNode(4, node2));
console.log(hasCycle(node1)); // 输出：true
技术细节：
- 快指针每次走两步，慢指针每次走一步
- 如果有环，快指针最终会追上慢指针
- 时间复杂度O(n)，空间复杂度O(1)
实际应用：内存管理中的循环引用检测、状态机验证等场景都会用到类似算法。
四、合并两个有序链表：链表界的连连看
合并有序链表就像玩连连看，需要比较两个链表的节点值，然后按顺序连接。这题可以用递归或迭代两种解法，咱们展示更简洁的递归解法。
递归实现如下：
function mergeTwoLists(l1, l2) {
if (!l1) return l2; // l1为空直接返回l2
if (!l2) return l1; // l2为空直接返回l1
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2); // 连接较小的节点
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
// 示例：合并 1->3->5 和 2->4->6
const l1 = new ListNode(1, new ListNode(3, new ListNode(5)));
const l2 = new ListNode(2, new ListNode(4, new ListNode(6)));
console.log(mergeTwoLists(l1, l2)); // 输出：1->2->3->4->5->6
迭代版本要点：
- 使用哨兵节点(dummy node)简化边界条件处理
- 维护一个当前指针逐步构建新链表
- 当一个链表遍历完后，直接连接另一个链表的剩余部分
应用场景：归并排序的基础操作、数据库多路归并等都需要这种合并能力。
五、技术选型与性能分析
这三种链表操作代表了不同的算法思想：
- 反转链表：指针操作基本功
- 环形检测：快慢指针的经典应用
- 合并链表：分治思想的入门案例
性能对比： | 操作 | 时间复杂度 | 空间复杂度 | |--------------|------------|------------| | 反转链表 | O(n) | O(1) | | 环形检测 | O(n) | O(1) | | 合并有序链表 | O(n+m) | O(1)或O(n+m) |
注意事项：
- 递归解法虽然简洁，但会有栈溢出风险
- 实际工程中要考虑链表长度，超长链表建议用迭代
- JavaScript引擎的尾调用优化不够可靠
六、举一反三：链表问题的解题套路
通过这三个题目，我们可以总结出链表问题的通用解法：
指针操作：多指针策略能解决大多数问题
- 反转用三指针
- 环检测用快慢指针
- 合并用双指针
递归思维：把问题分解为子问题
- 合并链表就是典型的递归应用
- 递归代码简洁但要注意栈深度
边界处理：链表问题最容易忽略边界条件
- 空链表处理
- 单节点链表
- 头尾节点特殊处理
七、总结与提升建议
链表操作是面试中的常客，掌握这些基础题目后，可以尝试更复杂的变种：
- 反转链表II（部分反转）
- 环形链表II（找出环的起点）
- K个一组反转链表
- 合并K个有序链表
建议学习路径：
- 先掌握这三种基础解法
- 然后尝试用不同方法实现（比如递归改迭代）
- 最后挑战更复杂的变种题目
记住，链表问题的核心就是指针操作，就像玩连连看一样，关键是不能断链。多画图、多调试，很快你就能成为链表问题的高手！
评论