当前位置：首页 > JavaScript

js实现反向链表

2026-04-07 07:55:15JavaScript

反转链表的实现方法

反转链表是常见的算法问题，可以通过迭代或递归两种方式实现。以下是JavaScript中的具体实现代码。

迭代法实现

迭代法通过遍历链表并逐个反转节点间的指针来实现反转。时间复杂度为O(n)，空间复杂度为O(1)。

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、current和nextTemp。每次迭代将current节点的next指针指向prev，然后移动指针继续处理下一个节点。

js实现反向链表

递归法实现

递归法通过递归调用反转剩余的链表，再将当前节点连接到已反转的部分。时间复杂度为O(n)，空间复杂度为O(n)（递归栈空间）。

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

    const reversedList = reverseList(head.next);
    head.next.next = head;
    head.next = null;

    return reversedList;
}

递归终止条件是链表为空或只有一个节点。递归过程先将后续链表反转，再将当前节点连接到反转后的链表末尾。

js实现反向链表

使用示例

假设有以下链表节点定义：

class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

创建链表并测试反转函数：

const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
node1.next = node2;
node2.next = node3;

const reversed = reverseList(node1);
console.log(reversed); // 输出反转后的链表