链表基础知识
约 1326 字大约 4 分钟
2025-03-21
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表的特点和数组相反:访问元素慢,新增或删除元素快。
链表的常用使用场景包括:
- LRU 缓存淘汰算法。
- 解决哈希冲突的哈希表。
- 各类缓冲池 和 栈 的实现。
好吧,好像都和前端都没有关系。使用大型数据集时,链表的大部分性能提升都会很明显。我们通常不会在前端处理这种大小的数据集。
链表在前端的主要应用场景是: 面试,哈哈。
面试中,考链表,可以了解面试者程序设计能力和实操能力。下面是一些链表的题目,来练练手吧:
- 单向链表,双向链表的实现。
- 反转链表。
- 使用循环链表解决约瑟夫环问题。
一、前端视角下的链表基础知识
1. 链表特点
- 节点结构:每个节点包含数据 + 指针(单链表只有next,双向链表有prev+next)
- 内存非连续:不需要预先分配连续内存空间
- 操作效率:插入/删除时间复杂度O(1),随机访问O(n)
- 前端常见应用:虚拟DOM树结构、React Fiber架构的任务队列、Undo/Redo历史记录栈
2. 链表 vs 数组
// 数组特点
const arr = [1, 2, 3];
arr.unshift(0); // 插入头部导致全体元素移动 O(n)
arr.splice(1, 0, 99); // 中间插入元素需要移动
// 链表实现
class Node {
constructor(val) {
this.val = val;
this.next = null;
// this.prev = null; // 双向链表
}
}二、经典链表题目与解法
1. 反转链表(高频考点)
问题:将 1→2→3→4→null 反转为 4→3→2→1→null
解法1-迭代法:
function reverseList(head) {
let prev = null;
let curr = head;
while (curr) {
const nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}解法2-递归法:
function reverseList(head) {
if (!head || !head.next) return head;
const newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}2. 环形链表检测
问题:判断链表是否有环
Floyd判圈法(快慢指针):
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;
}3. 合并两个有序链表
问题:合并两个升序链表为新升序链表
迭代法:
function mergeTwoLists(l1, l2) {
const dummy = new Node(-1);
let curr = dummy;
while (l1 && l2) {
if (l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = l1 || l2;
return dummy.next;
}三、链表解题思路体系
1. 双指针技巧
- 快慢指针:找中间节点、环形检测(快指针走2步/慢1步)
- 前后指针:删除倒数第N个节点(先走N步的指针)
function removeNthFromEnd(head, n) {
const dummy = new Node(0);
dummy.next = head;
let fast = dummy,
slow = dummy;
for (let i = 0; i <= n; i++) {
fast = fast.next;
}
while (fast) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}2. 递归法
适合处理反向操作、树形结构类问题
// 递归处理两数相加
function addTwoNumbers(l1, l2) {
const helper = (n1, n2, carry) => {
if (!n1 && !n2 && carry === 0) return null;
const sum = (n1?.val || 0) + (n2?.val || 0) + carry;
const newNode = new Node(sum % 10);
newNode.next = helper(n1?.next, n2?.next, Math.floor(sum / 10));
return newNode;
};
return helper(l1, l2, 0);
}3. 虚拟头节点(Dummy Node)
统一处理边界条件,避免单独处理头节点
// 删除重复元素
function deleteDuplicates(head) {
const dummy = new Node(0);
dummy.next = head;
let curr = dummy;
while (curr.next && curr.next.next) {
if (curr.next.val === curr.next.next.val) {
const val = curr.next.val;
while (curr.next && curr.next.val === val) {
curr.next = curr.next.next;
}
} else {
curr = curr.next;
}
}
return dummy.next;
}4. 哈希表/集合
检测重复节点、缓存节点信息
// 判断相交链表
function getIntersectionNode(headA, headB) {
const visited = new Set();
while (headA) {
visited.add(headA);
headA = headA.next;
}
while (headB) {
if (visited.has(headB)) return headB;
headB = headB.next;
}
return null;
}四、综合运用案例
重排链表(LCR 026):给定 1→2→3→4→5→null 变为 1→5→2→4→3→null
解题步骤:
- 快慢指针找中点
- 反转后半部分链表
- 合并前后两部分
function reorderList(head) {
if (!head || !head.next) return;
// 找中间节点
let slow = head,
fast = head;
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
// 反转后半部分
let prev = null,
curr = slow.next;
slow.next = null;
while (curr) {
const nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
// 合并链表
let p1 = head,
p2 = prev;
while (p2) {
const next1 = p1.next;
const next2 = p2.next;
p1.next = p2;
p2.next = next1;
p1 = next1;
p2 = next2;
}
}五、注意事项
- 边界处理:空链表、单节点链表、头尾节点操作
- 指针丢失:修改指针前保存后续节点引用
- 环形陷阱:遍历链表时注意终止条件
- 内存管理:JavaScript无需手动释放内存,但要注意循环引用
通过掌握这些基础操作和解题模板,配合画图分析指针走向,可以系统化解决大多数链表类算法问题。
参考文章:
