链表算法题解题思路与代码分析

1. 遍历访问类（虚拟头结点技巧）

核心解题思路

• 虚拟头结点（dummy node）：当需要对头结点进行删除或插入操作时，使用 dummy 节点可以统一处理所有节点，避免单独判断头结点的特殊情况。
• 遍历：用 prev 指针指向当前已处理链表的末尾，依次检查每个节点是否符合条件，决定是保留还是跳过。

经典例题：203. 移除链表元素

题目：删除链表中等于给定值 val 的所有节点。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    // 创建虚拟头结点，指向原链表头部
    const dummy = new ListNode(0);
    dummy.next = head;
    
    let prev = dummy;      // prev 指向已处理链表的最后一个节点
    let curr = head;       // curr 为当前待检查的节点
    
    while (curr !== null) {
        if (curr.val === val) {
            // 如果当前节点需要删除，则将 prev.next 指向 curr.next（跳过当前节点）
            prev.next = curr.next;
        } else {
            // 不需要删除，则移动 prev 到当前节点
            prev = curr;
        }
        // 无论是否删除，curr 都向后移动
        curr = curr.next;
    }
    
    return dummy.next; // 返回真正的头结点
};

关键点：

• 使用 dummy 节点简化头结点删除的逻辑。
• 始终维护 prev 指向已处理链表的末尾，方便删除时修改 next 指针。

2. 反转类（指针修改的核心考点）

核心解题思路

• 迭代法（双指针）：定义 prev、curr 两个指针，遍历链表时修改 curr.next 指向 prev，然后整体向前移动。
• 递归法：假设后续链表已反转，只需处理当前节点与已反转部分的连接。

经典例题：206. 反转链表

题目：反转一个单链表。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 方法一：迭代
var reverseList = function(head) {
    let prev = null;
    let curr = head;
    
    while (curr !== null) {
        const next = curr.next; // 暂存下一个节点
        curr.next = prev;       // 将当前节点指向前一个节点（反转）
        prev = curr;            // prev 前移
        curr = next;            // curr 前移
    }
    
    return prev; // 最后 prev 成为新头结点
};

// 方法二：递归（有助于理解递归思想）
var reverseListRecursive = function(head) {
    // 递归终止条件：空链表或只有一个节点
    if (head === null || head.next === null) {
        return head;
    }
    // 递归反转后续链表
    const newHead = reverseListRecursive(head.next);
    // 将当前节点的下一个节点的 next 指向当前节点
    head.next.next = head;
    // 断开当前节点原来的 next，防止循环
    head.next = null;
    return newHead;
};

关键点：

• 迭代法需要三个指针 prev、curr、next 配合。
• 递归法思考：先反转后续，再处理当前节点。

3. 双指针技巧类（快慢指针 / 前后指针）

核心解题思路

• 快慢指针：两个指针以不同速度移动，常用于检测环、找中点等。
• 前后指针（固定距离）：一个指针先走 k 步，然后两个指针同步前进，可以找到倒数第 k 个节点。

经典例题：141. 环形链表

题目：判断链表中是否有环。

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if (head === null || head.next === null) return false;
    
    let slow = head;
    let fast = head.next;
    
    while (slow !== fast) {
        // 如果快指针到达末尾，说明无环
        if (fast === null || fast.next === null) {
            return false;
        }
        slow = slow.next;      // 慢指针走一步
        fast = fast.next.next; // 快指针走两步
    }
    // 快慢指针相遇，说明有环
    return true;
};

关键点：

• 快指针每次走两步，慢指针走一步，如果有环它们必定相遇。
• 注意边界条件：空链表或只有一个节点且无环。

4. 链表合并与分解

核心解题思路

• 合并有序链表：使用双指针分别遍历两个链表，比较节点值，将较小者接入结果链表（通常使用 dummy 节点）。
• 分解：将原链表拆分成多个子链表，然后按规则重新拼接。

经典例题：21. 合并两个有序链表

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

/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    // 创建虚拟头结点，方便结果链表的构建
    const dummy = new ListNode(0);
    let cur = dummy; // cur 指向结果链表的最后一个节点
    
    let l1 = list1;
    let l2 = list2;
    
    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next; // cur 指针后移
    }
    
    // 处理剩余部分（直接连接即可）
    cur.next = l1 !== null ? l1 : l2;
    
    return dummy.next;
};

关键点：

• 使用 dummy 节点简化头结点的处理。
• 最后只需将剩余链表直接接上，无需逐个遍历。

5. 复杂结构类（带随机指针 / 多级指针）

核心解题思路

• 哈希表映射法：第一遍遍历，用 Map 存储原节点到新节点的映射；第二遍遍历，根据映射关系设置新节点的 next 和 random 指针。
• 原地复制法（空间 O(1)）：将新节点插入到原节点之后，然后处理 random 指针，最后拆分链表。

经典例题：138. 复制带随机指针的链表

题目：实现一个函数，复制一个复杂链表（每个节点有一个 random 指针指向任意节点或 null）。

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
// 哈希表法（易于理解）
var copyRandomList = function(head) {
    if (head === null) return null;
    
    const map = new Map();
    let curr = head;
    
    // 第一遍：创建所有新节点，建立原节点 -> 新节点的映射
    while (curr !== null) {
        map.set(curr, new Node(curr.val));
        curr = curr.next;
    }
    
    curr = head;
    // 第二遍：设置新节点的 next 和 random
    while (curr !== null) {
        const newNode = map.get(curr);
        // next 指针：新节点的 next 指向原节点 next 对应的新节点
        newNode.next = curr.next ? map.get(curr.next) : null;
        // random 指针同理
        newNode.random = curr.random ? map.get(curr.random) : null;
        curr = curr.next;
    }
    
    return map.get(head);
};

关键点：

• 利用哈希表建立新旧节点的对应关系，两次遍历完成复制。
• 注意空指针的处理。

6. 排序与旋转

核心解题思路

• 排序链表：链表排序通常用归并排序（自顶向下或自底向上）。自顶向下需要找中点、递归排序、合并。
• 旋转链表：先成环，然后找到新的头尾节点断开。

经典例题：148. 排序链表

题目：给你链表的头结点 head，请将其按升序排列并返回排序后的链表。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    // 递归终止条件：空链表或只有一个节点
    if (head === null || head.next === null) return head;
    
    // 1. 找中点（快慢指针）
    let slow = head;
    let fast = head.next;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 此时 slow 指向中点（前半部分的最后一个节点）
    const rightHead = slow.next; // 右半部分的头结点
    slow.next = null;            // 切断链表
    
    // 2. 递归排序左右两部分
    const left = sortList(head);
    const right = sortList(rightHead);
    
    // 3. 合并两个有序链表
    return mergeTwoLists(left, right);
};

// 辅助函数：合并两个有序链表（前面已实现）
function mergeTwoLists(l1, l2) {
    const dummy = new ListNode(0);
    let cur = dummy;
    while (l1 && l2) {
        if (l1.val < l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    cur.next = l1 ? l1 : l2;
    return dummy.next;
}

关键点：

• 归并排序在链表上的实现：找中点、递归、合并。
• 注意快指针从 head.next 开始，确保偶数个节点时 slow 落在中间靠左位置。

总结

1. 每道题先尝试自己写一遍，再对照代码分析理解细节。
2. 重点掌握 虚拟头结点、双指针、反转模板 和 归并模板，这些技巧在后续刷题中会频繁用到。
3. 遇到复杂的指针操作，一定要画图辅助理解。