206. 反转链表

Origin: LeetCode 206

题目描述

给定单链表的头节点 head，反转链表，返回反转后的头节点。

示例

Input: head = [1, 2, 3, 4, 5] Output: [5, 4, 3, 2, 1]

Input: head = [1, 2] Output: [2, 1]

Input: head = [] Output: []

约束

• 链表中节点数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

关键信息

• 面试必考题
• 你做过 HackerRank 第 34 题（链表反转），做过题型笔记”链表解题”
• 迭代：三指针 prev/curr/next
• 递归也能做

Resolution

我的解法

function reverseList(head: ListNode | null): ListNode | null {
    if (!head || !head.next) return head
    let cur: ListNode | null = head
    let pre: ListNode | null = null
 
    while (cur) {
        let next: ListNode | null = cur.next
        cur.next = pre
        pre = cur
        cur = next
    }
    return pre
}

取巧解法（转数组 + 重建）

function reverseList(head: ListNode | null): ListNode | null {
    if (!head) return head
    let cur: ListNode | null = head
    const arr = []
    while (cur) {
        arr.push(cur.val)
        cur = cur.next
    }
    let dummy = new ListNode()
    cur = dummy
    arr.reverse().forEach((val) => {
        cur!.next = new ListNode(val)
        cur = cur!.next
    })
    return dummy.next
}

解题思路

三指针 prev/curr/next。每轮四步：

1. next = cur.next（先存下一个）
2. cur.next = pre（反转指针）
3. pre = cur（pre 前进）
4. cur = next（cur 前进）

遍历完 pre 就是新的头节点。

复杂度

• 时间：O(n)
• 空间：O(1)（标准解法）/ O(n)（取巧解法）