[算法] js 如何反转链接列表？

在JavaScript中，反转链表是一个常见的算法问题，主要涉及到重新排列链表中的节点，使得原链表中的第一个节点变成最后一个节点，最后一个节点变成第一个节点。这个操作通常需要改变节点之间的链接方向。

假设我们有一个简单的单向链表的节点类定义如下：

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

接下来，我们将写一个函数来反转链表。这个函数将接受链表的头节点作为输入，并返回新的头节点（即原链表的尾节点）。反转链表的基本思路是遍历原链表，依次改变每个节点的 next 指针，使其指向前一个节点。我们可以通过定义一个变量 prev 来记录当前节点的前一个节点，初始时 prev 为 null，因为反转后的新链表的头节点的 next 应该是 null。

以下是具体的实现代码：

javascript
function reverseList(head) {
    let prev = null;    // 初始时没有前一个节点
    let current = head; // 从头节点开始遍历

    while (current !== null) {
        let next = current.next; // 临时保存当前节点的下一个节点
        current.next = prev;     // 将当前节点指向前一个节点
        prev = current;          // 前一个节点前移
        current = next;          // 当前节点前移
    }

    return prev; // 最后prev将会是新的头节点
}

示例：

假设我们有一个链表 1 -> 2 -> 3 -> null，调用 reverseList 函数后，链表应该变成 3 -> 2 -> 1 -> null。

复杂度分析：

• 时间复杂度：O(n)，我们需要遍历链表一次，n 是链表的长度。
• 空间复杂度：O(1)，我们只使用了几个辅助变量，不依赖于输入链表的大小。

这种方法很直观，也很高效。在实际开发中，如果需要处理链表的问题，这种技巧是非常有用的。