当前位置：首页 > JavaScript

js实现反向链表

2026-03-15 14:32:14JavaScript

实现反向链表的方法

迭代法

迭代法是最常见且高效的反转链表方法，通过遍历链表并逐个反转节点指针实现。

js实现反向链表

function reverseList(head) {
    let prev = null;
    let current = head;
    while (current !== null) {
        const nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

prev 用于保存前一个节点，初始化为 null。
current 指向当前节点，初始化为链表头 head。
在循环中，临时保存 current.next，将 current.next 指向 prev，然后更新 prev 和 current 为下一个节点。
最终返回 prev，即新的链表头。

递归法

递归法通过递归调用反转子链表，再将当前节点连接到反转后的子链表尾部。

js实现反向链表

function reverseList(head) {
    if (head === null || head.next === null) {
        return head;
    }
    const newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

基线条件：链表为空或只有一个节点时直接返回。
递归反转 head.next 开始的子链表，返回新的头节点 newHead。
将当前节点 head 连接到反转后的子链表尾部（head.next.next = head），并断开原链接（head.next = null）。
返回 newHead 作为最终结果。

使用栈结构

利用栈的先进后出特性反转链表，适合非原地修改的场景。

function reverseList(head) {
    if (head === null) return null;
    const stack = [];
    let current = head;
    while (current !== null) {
        stack.push(current);
        current = current.next;
    }
    const newHead = stack.pop();
    current = newHead;
    while (stack.length > 0) {
        current.next = stack.pop();
        current = current.next;
    }
    current.next = null;
    return newHead;
}