ZhenYu's 知识库

外观

链表基础知识

约 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
解题步骤：

  1. 快慢指针找中点
  2. 反转后半部分链表
  3. 合并前后两部分
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;
    }
}

五、注意事项

  1. 边界处理：空链表、单节点链表、头尾节点操作
  2. 指针丢失：修改指针前保存后续节点引用
  3. 环形陷阱：遍历链表时注意终止条件
  4. 内存管理：JavaScript无需手动释放内存，但要注意循环引用

通过掌握这些基础操作和解题模板，配合画图分析指针走向，可以系统化解决大多数链表类算法问题。

参考文章：