反转链表js实现

反转链表的 JavaScript 实现

反转链表是数据结构中的常见操作，以下是几种实现方法：

迭代法

通过遍历链表并逐个反转节点指针实现：

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;
}

该方法时间复杂度为 O(n)，空间复杂度为 O(1)。

递归法

利用递归栈实现反向操作：

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;
}

递归实现的时间复杂度为 O(n)，空间复杂度为 O(n)（递归栈空间）。

双指针法

优化迭代法的另一种写法：

function reverseList(head) {
    let [prev, curr] = [null, head];
    while (curr) {
        [curr.next, prev, curr] = [prev, curr, curr.next];
    }
    return prev;
}

使用解构赋值简化指针交换操作。

注意事项

1. 处理空链表或单节点链表的边界情况
2. 反转后原链表的头节点应指向 null
3. 递归实现可能导致栈溢出（超长链表情况下）

实际应用中可根据具体场景选择迭代（推荐）或递归实现。