反轉 Linked List

完成的程式碼

func reverse(_ listNode: ListNode?) -> ListNode? {
    var previous: ListNode? = nil
    var current = listNode
    var next: ListNode? = nil

    while current != nil {
        next = current?.next
        current?.next = previous
        previous = current
        current = next
    }
    
    return previous
}

邏輯

設定必要的 flags 和初始值

var previous: ListNode? = nil
var current = listNode
var next: ListNode? = nil

previous 和 next 是在反轉替換過程中用來暫存節點的 flags

Routine

透過走訪和指標替換的邏輯，來達到反轉 linked list 的目的

while current != nil {
    next = current?.next
    current?.next = previous
    previous = current
    current = next
}

當 current 為空值的時候

• 這個 linked list 本來就是空的
• 已經走訪完這個 linked list

就可以結束 routines 。

初始狀態

以這個 linked list 為例

C
1 -> 2 -> 3 -> 4

第一 routine

更新 next ，避免接下來 current 換掉 next node 的時候失去參照

// next = current?.next

C    N
1 -> 2 -> 3 -> 4

更新 current?.next ，指向 previous 。
在第一步驟 P 是空值，因此是指向 nil

// current?.next = previous

C    N
1    2 -> 3 -> 4
|  
+--> nil
     P

結束替換，將 previous 換到 current

// previous = current

P
C    N
1    2 -> 3 -> 4
|  
+--> nil

current 換到 next 的位置準備下一次的替換

// current = next

     C
P    N
1    2 -> 3 -> 4
|  
+--> nil

結束 Routines

從上面的圖可以發現 previous 在結束每次 routine 之後都會指向反轉後 linked list 的節點
因此可以直接回傳 previous 做為結果

return previous

分析

時間複雜度 -> O(n)

線性複雜度，因為每一個節點只有走訪過一次

空間複雜度 -> O(1)

我們只有宣告 flag 用途的變數，也沒有宣告新的物件因此是常數複雜度 O(1)

ListNode 的資料結構

基本的 singly linked list 的節點，有兩個 properties ：

• value 用來存值
• next 用來指向下一個節點

實作和 initializer 參照 LeetCode 。
另外加上方便 debug 用的 helper Method

class ListNode {
    var value: Int
    var next: ListNode?

    init() {
        self.value = 0
        self.next = nil
    }

    init(_ value: Int) { 
        self.value = value
        self.next = nil
    }

    init(_ value: Int, _ next: ListNode?) {
        self.value = value
        self.next = next
    }

    // MARK: - Helper Method

    var array: [Int] {
        var result = [Int]()
        var current: ListNode? = self
        while current != nil {
            result.append(dummy!.value)
            current = current?.next
        }
        return result
    }
}