206. Reverse Linked List

題目連結

思路

反轉 LinkedList 是 LinkedList 相關的題目當中比較經典的一個題目，題目的要求是把原先的 LinkedList 整個倒轉過來，也就是將箭頭的方向 180 度的調換。

此題同樣也會運用到雙指標的方法來進行迭代處理，在初始狀態下會有 prev 和 cur 兩個指標，分別放置在空的節點以及 head 上，後續每次迭代的操作是：

1. 用一個 tmp 暫存 cur.next

2. 將 cur.next 指向 prev

3. 將 prev 移動到 cur

4. 將 cur 移動到 tmp

整個流程可以用下面的動圖來呈現，當 cur 走到 null 的時候就代表交換完畢，最後要回傳的指標則是 prev，代表以它作為新的 head~

Full Code

Golang

func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }

    var prev *ListNode
    cur := head

    for cur != nil {
        tmp := cur.Next
        cur.Next = prev
        prev = cur
        cur = tmp
    }

    return prev
}