24. Swap Nodes in Pairs

題目連結

思路

此題有點像是反轉 LinkedList的一個小變形，要將 LinkedList 中的節點兩個為一對進行順序的反轉，例如 1 -> 2 -> 3-> 4 會變成 2 -> 1 -> 4 -> 3，遇到奇數個節點的時候剩下的那個節點則不做處理。在實作上也一樣會利用到雙指標來進行，但相較於單純的反轉 LinkedList 來說每次迭代需要考慮的東西會更複雜一點點，另外為了處理上的方便，可以使用一個 Dummy Head 作為起點，其指向會是原先的 head。

一開始的配置會像是下面這樣，將 prev 指標放置在 dummy 節點，而 cur 則是在原先的 head 上。

在每一輪的迭代處理當中，我們會聚焦在四個節點上，分別是主要進行交換的兩個節點，以及各自前後的一個節點，像是以下面的狀況來說，在第一輪我們會關注 dummy、1、2 和 3 這幾個節點，由於要進行主要的順序調換，以及維護好前後節點之間的指向關係，因此每一步的操作都需要考慮清楚才不會導致到最後已經不知道節點指到哪裡去了...

每一輪中具體的操作步驟如下：(會以第一輪的操作為例代入實際的值)

1. 使用 tmp 暫存 cur.next.next (把 3 暫存起來)

2. prev.next 指向 cur.next (dummy 指向 2，這邊做這樣的處理是為了後續的指向關係維護以及最後的回傳)

3. cur.next.next = cur (2 指向 1，主要的順序交換步驟)

4. cur.next = tmp (1 指向 3，把這一對的指向放到下一對上)

5. prev = cur; cur = cur.next (移動 prev 和 cur)

上面的動圖呈現了大致上的操作流程 (有部分步驟合併在一起呈現)，可以注意到上方第二步的 dummy 指向 2，在第二輪就變成了 1 指向 4，最後當 cur 指到 nil 的時候即完成。另外是考慮到奇數個節點的時候，會在 cur 指到最後一個節點的時候就提前結束，因此在每一輪開始的時候可以先判斷 cur.next = null? 來確認是否已經走到最後一個節點上了。

還有就是最後要回傳的東西，因為 head 是沒有被處理的，所以它還是會指向一開始的 1 身上，所以並不是正確的開頭，而是應該要回傳 dummy.next 才會是調換過後的新的開頭~

Full Code

Golang

func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{-1, head}

    prev := dummy
    cur := dummy.Next

    for cur != nil {
        if cur.Next == nil {
            return dummy.Next
        }

        tmp := cur.Next.Next
        prev.Next = cur.Next
        cur.Next.Next = cur
        cur.Next = tmp
        prev = cur
        cur = cur.Next
    } 

    return dummy.Next
}