206. 反转链表

[Geekhyt]

原题链接

迭代

1.初始化哨兵节点 prev 为 null，及当前节点 curr 指向头节点。
2.开始迭代，记录 next 指针留备后用，反转指针。
3.推进指针继续迭代，最后返回新的链表头节点 prev。

const reverseList = function(head) {
    let prev = null;
    let curr = head;
    while (curr !== null) {
        // 记录 next 节点
        let next = curr.next;
        // 反转指针
        curr.next = prev;
        // 推进指针
        prev = curr;
        curr = next;
    }
    // 返回翻转后的头节点
    return prev;
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

递归

const reverseList = function(head) {
    if (!head || !head.next) return head;
    // 记录当前节点的下一个节点
    let next = head.next;
    let reverseHead = reverseList(next);
    // 操作指针进行反转
    head.next = null;
    next.next = head;
    return reverseHead;
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)