理解链表算法：从基础操作到高级应用-洪萨配资

理解链表算法：从基础操作到高级应用

链表是算法面试中最高频的考点之一，其「非连续存储」的特性决定了它的解题思路和数组有本质区别——指针操作、边界处理、虚拟头节点等技巧贯穿始终。本文将从链表的核心解题思想出发，拆解合并、分解、指针技巧、运算四大类经典题型，结合LeetCode高频题给出最优解，并标注面试中最容易踩坑的易错点。

一、核心解题思想：先掌握这3个通用技巧

在开始刷题前，先牢记链表题的「三板斧」，能解决80%的问题：

1. 虚拟头节点（Dummy Node）

适用场景：需要创建/修改链表（如合并、删除、分解），避免处理「头节点为空」的边界情况。

核心价值：让「删除头节点」和「删除中间节点」、「创建新链表头」和「拼接后续节点」的逻辑完全统一。

示例：合并两个链表时，用dummy = new ListNode(-1)作为占位符，最终返回dummy.next即可。

2. 双指针技巧

链表的绝大多数经典问题（中点、倒数k、环、相交）都依赖双指针，核心是通过指针的「步长差」或「路径差」实现目标：

快慢指针：慢指针走1步，快指针走2步（中点、环检测）；
前后指针：前驱指针记录「待删除节点的前一个节点」（删除重复、倒数k）；
互换指针：遍历完A链表接B链表，遍历完B链表接A链表（链表相交）。

3. 栈/堆的辅助使用

栈：解决「正序链表逆序操作」（如445题两数相加II，正序链表转逆序取数）；
最小堆（优先队列）：解决「多链表合并」（如合并k个升序链表、有序矩阵找第k小）。

二、经典题型拆解（附最优解+易错点）

（一）链表的合并：从2个到k个，再到矩阵/数组的「伪合并」

合并类问题的核心是「筛选最小值/符合条件的值，按序拼接」，从基础的2个链表合并，可延伸到k个链表、有序矩阵等场景。

1. 合并两个升序链表（LeetCode 21）

题目要求：将两个升序链表合并为一个新的升序链表。

核心思路：双指针「拉拉链」——两个指针分别遍历两个链表，每次选值更小的节点接入新链表，遍历完一个后直接拼接另一个的剩余部分。

JavaScript

/** * @param {ListNode} l1 - 升序链表1 * @param {ListNode} l2 - 升序链表2 * @returns {ListNode} 合并后的升序链表 */ function mergeTwoLists(l1, l2) { // 虚拟头节点：避免处理l1/l2为空的情况 const dummy = new ListNode(-1); let p = dummy; // 新链表的尾指针 let p1 = l1, p2 = l2; // 核心：选更小的节点接入新链表 while (p1 !== null && p2 !== null) { if (p1.val <= p2.val) { p.next = p1; p1 = p1.next; } else { p.next = p2; p2 = p2.next; } p = p.next; // 尾指针后移 } // 拼接剩余节点（剩余部分本身有序） p.next = p1 === null ? p2 : p1; return dummy.next; }

易错点：

忘记拼接剩余节点，导致结果缺失部分链表；
尾指针p未后移，始终覆盖dummy.next，最终只保留最后一个节点。

2. 合并k个升序链表（LeetCode 23）

题目要求：合并k个升序链表，返回合并后的升序链表。

核心思路：最小堆筛选最小值——用堆存储各链表的当前节点，每次取堆顶（最小值）接入新链表，再将该链表的下一个节点入堆。

JavaScript

/** * @param {ListNode[]} lists - k个升序链表数组 * @returns {ListNode} 合并后的链表 */ var mergeKLists = function(lists) { const k = lists.length; if (k === 0) return null; // 定义最小堆（按节点值排序） class MinHeap { constructor() { this.heap = []; } push(node) { this.heap.push(node); this.swim(this.heap.length - 1); } pop() { const min = this.heap[0]; const last = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = last; this.sink(0); } return min; } // 上浮：维护小顶堆 swim(idx) { while (idx > 0) { const parent = Math.floor((idx - 1) / 2); if (this.heap[parent].val > this.heap[idx].val) { [this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]]; idx = parent; } else break; } } // 下沉：维护小顶堆 sink(idx) { while (idx * 2 + 1 < this.heap.length) { let minIdx = idx * 2 + 1; const right = idx * 2 + 2; if (right < this.heap.length && this.heap[right].val < this.heap[minIdx].val) { minIdx = right; } if (this.heap[idx].val < this.heap[minIdx].val) break; [this.heap[idx], this.heap[minIdx]] = [this.heap[minIdx], this.heap[idx]]; idx = minIdx; } } isEmpty() { return this.heap.length === 0; } } const dummy = new ListNode(-1); let p = dummy; const minHeap = new MinHeap(); // 初始化堆：各链表的第一个节点入堆 for (let i = 0; i < k; i++) { if (lists[i] !== null) minHeap.push(lists[i]); } // 循环取堆顶，拼接链表 while (!minHeap.isEmpty()) { const minNode = minHeap.pop(); p.next = minNode; p = p.next; // 该链表的下一个节点入堆 if (minNode.next !== null) minHeap.push(minNode.next); } return dummy.next; };

易错点：

堆的比较逻辑写错（如写成大顶堆），导致取到最大值；
忘记将「当前节点的下一个节点」入堆，堆很快为空，只合并了各链表的第一个节点；
未处理lists中包含null的情况，入堆时报错。

3. 延伸：有序矩阵中第K小的元素（LeetCode 378）

核心思路：将「矩阵的每一行」视为「升序链表」，复用「合并k个链表」的堆思路——每行一个指针，堆存储「行索引+当前值」，每次取最小值后将该行下一个值入堆。

js

/** * 通用优先队列实现（支持大顶堆/小顶堆，基于完全二叉树+数组存储） * @param {Function} compareFn - 比较函数，决定堆类型： * 返回值是负数的时候，第一个参数的优先级更高 * - 小顶堆（默认）：(a,b) => a - b（返回负数则a优先级高） * - 大顶堆：(a,b) => b - a（返回负数则b优先级高） */ class PriorityQueue1 { constructor(compareFn = (a, b) => a - b) { this.compareFn = compareFn; // 自定义比较函数（核心：替代硬编码比较） this.size = 0; // 堆的有效元素个数（≠queue.length，避免数组空洞） this.queue = []; // 物理存储数组（逻辑完全二叉树） } // 入队：添加元素并上浮堆化 enqueue(val) { // 1. 把新元素放到数组末尾（完全二叉树的最后一个节点） this.queue[this.size] = val; // 2. 上浮：维护堆的性质（从新元素位置向上调整） this.swim(this.size); // 3. 有效元素个数+1（先swim再++，因为swim需要当前索引） this.size++; } // 出队：移除并返回堆顶元素，最后一个元素补位后下沉堆化 dequeue() { // 边界：空队列返回null if (this.size === 0) return null; // 1. 保存堆顶元素（要返回的值） const peek = this.queue[0]; // 2. 最后一个元素移到堆顶（完全二叉树补位） this.queue[0] = this.queue[this.size - 1]; // 3. 下沉：维护堆的性质（从堆顶向下调整） this.sink(0); // 4. 有效元素个数-1（堆大小减小） this.size--; // 可选：清空数组空洞（非必需，但更优雅） this.queue.length = this.size; return peek; } // 获取堆顶元素（不出队） head() { return this.size === 0 ? null : this.queue[0]; } // 获取父节点索引 parent(idx) { return Math.floor((idx - 1) / 2); } // 获取左子节点索引 left(idx) { return idx * 2 + 1; } // 获取右子节点索引 right(idx) { return idx * 2 + 2; } // 交换两个节点的值 swap(idx1, idx2) { [this.queue[idx1], this.queue[idx2]] = [this.queue[idx2], this.queue[idx1]]; } // 上浮（swim）：从idx向上调整，维护堆性质 swim(idx) { // 循环：直到根节点（idx=0）或当前节点不小于父节点 while (idx > 0) { const parentIdx = this.parent(idx); // 核心：用compareFn替代硬编码比较 // compareFn(a,b) < 0 → a优先级更高（应上浮） if (this.compareFn(this.queue[idx], this.queue[parentIdx]) >= 0) { break; // 当前节点优先级不高于父节点，停止上浮 } // 交换当前节点和父节点 this.swap(idx, parentIdx); // 继续向上检查 idx = parentIdx; } } // 下沉（sink）：从idx向下调整，维护堆性质 sink(idx) { // 循环：直到没有左子节点（完全二叉树，左子不存在则右子也不存在） while (this.left(idx) < this.size) { const leftIdx = this.left(idx); const rightIdx = this.right(idx); // 找到“优先级更高”的子节点（小顶堆找更小的，大顶堆找更大的） let priorityIdx = leftIdx; // 右子节点存在，且右子优先级更高 → 切换到右子 if (rightIdx < this.size && this.compareFn(this.queue[rightIdx], this.queue[leftIdx]) < 0) { priorityIdx = rightIdx; } // 当前节点优先级 ≥ 子节点 → 停止下沉 if (this.compareFn(this.queue[idx], this.queue[priorityIdx]) <= 0) { break; } // 交换当前节点和优先级更高的子节点 this.swap(idx, priorityIdx); // 继续向下检查 idx = priorityIdx; } } // 辅助：判断队列是否为空 isEmpty() { return this.size === 0; } } /** * @param {number[][]} matrix * @param {number} k * @return {number} */ var kthSmallest = function(matrix, k) { const rows = matrix.length const cols = matrix[0].length // 每一行，都有一个指针，pArr[0]表示第0行的指针，pArr[1]表示第1行的指针， let pArr = new Array(rows).fill(0) // 返回值 let res // 这里因为需要存储第几行的信息，所以queue队列里存储的不单单是val 还有row的信息，这样的话，需要重新写compareFn const pq = new PriorityQueue1(([row1,val1],[row2,val2])=>val1-val2) // 每行的第一个元素进队 for(let row=0;row<rows;row++){ pq.enqueue([row,matrix[row][0]]) } // 当队存在且k>0的时候说明需要继续 while(pq.size>0 && k>0){ // 出队的是当前最小的 const [curRow,curVal] = pq.dequeue() // 值存下 res = curVal // 循环k次就能获取到k小的值 k-- const nextCol = pArr[curRow]+1 if(nextCol<cols){ pArr[curRow] = nextCol pq.enqueue([curRow,matrix[curRow][nextCol]]) } } return res };

易错点：

堆中仅存储值，未记录行索引，无法找到下一个要入堆的值；
忽略矩阵单行/单列的边界情况。

（二）链表的分解：按条件拆分，删除重复

分解类问题的核心是「用两个虚拟头节点分别存储符合/不符合条件的节点，最后拼接」。

1. 分隔链表（LeetCode 86）

题目要求：将链表分隔为两部分，小于x的节点在前，大于等于x的节点在后，保持原有相对顺序。

核心思路：两个虚拟头节点分别存储「小于x」和「大于等于x」的节点，遍历原链表后拼接。

JavaScript

易错点：

未断开p2.next，若原链表末尾属于「大于等于x」的部分，会导致链表成环；
拼接时错误拼接p2Dummy而非p2Dummy.next，引入无效的虚拟头节点。

2. 删除排序链表中的重复元素II（LeetCode 82）

题目要求：删除链表中所有重复的节点，只保留原链表中没有重复出现的节点。

核心思路：前驱指针+跳过重复项——前驱指针记录「最后一个不重复的节点」，遍历指针找到所有连续重复节点后，前驱指针跳过这些节点。

JavaScript

易错点：

内层循环未判空p && p.next，导致p.next.val报错；
无重复时忘记移动前驱指针prev，prev始终停留在虚拟头节点，最终结果缺失部分节点；
仅删除重复节点中的一个，而非全部跳过。

（三）双指针经典：中点、倒数k、环、相交

这类问题的核心是「通过指针的步长/路径设计，一次遍历完成目标」，避免先遍历统计长度的二次遍历。

1. 链表的中间节点（LeetCode 876）

题目要求：返回链表的中间节点，偶数长度返回第二个中间节点。

核心思路：快慢指针——慢指针走1步，快指针走2步，快指针到末尾时，慢指针即为中间节点。

JavaScript

var middleNode = function(head) { if (head === null) return null; let slow = head, fast = head; // 循环条件：fast和fast.next都不为空 while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } return slow; };

易错点：

循环条件漏写fast或fast.next，导致fast.next.next报错；
混淆偶数长度的返回值（要求返回第二个中间节点，快慢指针的逻辑天然满足）。

2. 删除链表的倒数第N个节点（LeetCode 19）

核心思路：快慢指针拉开N步距离——快指针先前进N步，然后快慢指针同步前进，快指针到末尾时，慢指针指向倒数第N个节点的前驱。

JavaScript

易错点：

未使用虚拟头节点，删除倒数第L个节点（头节点）时出错；
快指针前进n步时未判空，n超过链表长度时报错；
循环条件写成fast !== null，导致慢指针位置错误。

3. 环形链表II（LeetCode 142）

题目要求：判断链表是否有环，若有则返回环的入口节点。

核心思路：快慢指针分两步——

判环：慢1快2，相遇则有环；
找入口：相遇后慢指针回头部，快慢均走1步，再次相遇即为入口。

JavaScript

原理推导：

设a=表头到入口的距离，b=入口到相遇点的距离，c=相遇点回到入口的距离：

快指针路程：2(a+b) = a + b + n*(b+c) → a = (n-1)*(b+c) + c；
当n=1时，a=c，因此慢指针回头部后，同步走必然在入口相遇。

易错点：

相遇后快指针未改为走1步，仍走2步，无法找到入口；
判环时循环条件漏写fast.next，导致报错；
忽略单节点成环的情况（如head.next = head）。

4. 相交链表（LeetCode 160）

题目要求：找到两个单链表相交的起始节点，无相交则返回null。

核心思路：互换指针——p1遍历完A接B，p2遍历完B接A，总路程均为A+B，相交则在交点相遇，否则同时到null。

JavaScript

var getIntersectionNode = function(headA, headB) { if (headA === null || headB === null) return null; let p1 = headA, p2 = headB; while (p1 !== p2) { p1 = p1 === null ? headB : p1.next; p2 = p2 === null ? headA : p2.next; } return p1; };

易错点：

担心无限循环：无需担心，p1/p2总路程相等，最终必相遇（要么交点，要么null）；
遍历到末尾时未切换到另一个链表，而是直接返回null。

（四）链表运算：两数相加（逆序/正序）

链表运算的核心是「模拟手工运算」，结合栈处理正序链表的逆序操作。

1. 两数相加（LeetCode 2）

题目要求：两个逆序存储数字的链表，返回相加后的逆序链表。

核心思路：模拟手工加法——遍历链表，逐位相加，处理进位。

JavaScript

2. 两数相加II（LeetCode 445）

题目要求：两个正序存储数字的链表，返回相加后的正序链表。

核心思路：栈逆序取数 + 反向构建链表——先将正序链表入栈，逆序取数相加，再反向构建正序链表。

JavaScript

易错点：

循环条件漏写isNeedPlusOne，漏掉末尾进位（如999+1=1000）；
反向构建链表时next指向写反（如head.next = newNode），导致链表断裂；
栈取数用shift()而非pop()，取数顺序错误。

三、面试高频易错点总结（避坑指南）

场景	常见错误	正确做法
虚拟头节点	返回head而非dummy.next	始终返回dummy.next，避免头节点被删除/修改
链表拼接	未断开尾节点的next	拼接前将尾节点next置为null，避免成环
快慢指针	循环条件漏写fast.next	判环/中点时用while (fast && fast.next)
堆/栈	堆的比较逻辑写错（大顶堆/小顶堆混淆）	小顶堆用a.val - b.val，大顶堆用b.val - a.val
反向构建链表	next指向写反	正确逻辑：newNode.next = head; head = newNode
进位处理	进位判断在取余之后	先判断val >= 10，再取余val % 10