算法_反向鏈表 - 今是昨非

Algorithem_ReverseLinkedList#

給定一個單鏈表的頭節點，反轉該鏈表，並返回反轉後的鏈表。

範例 1:

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

範例 2:

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

範例 3:

Input: head = []
Output: []

限制條件:

鏈表中的節點數量範圍為 [0, 5000]。
-5000 <= Node.val <= 5000

後續問題：鏈表可以通過迭代或遞歸的方式進行反轉。你能實現兩種方法嗎？

解法一#

先撇開後續問題，最直接的解法是，我把 LinkNode 轉為數組，然後數組逆序，再生成新的 LinkNode。

代碼如下：


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        
        var newNode = head
        var nodeList: [Int] = []
        while newNode != nil {
            nodeList.append(newNode!.val)
            newNode = newNode?.next
        }
        
        var resultNode = ListNode(nodeList[nodeList.count - 1])
        var tempNode: ListNode?
        for i in 0...nodeList.count - 2 {
            let item = nodeList[nodeList.count - 2 - i]
            let generateNode = generateNewNode(item)
            if tempNode == nil {
                resultNode.next = generateNode
            }
            else {
                tempNode?.next = generateNode
            }
            tempNode = generateNode
        }
        
        return resultNode
    }
    
    func generateNewNode(_ val: Int) -> ListNode? {
        return ListNode(val)
    }
}

解法二#

這裡理解比較麻煩，可參考，Reverse a linked list，頁面最下方的視頻，多看幾遍。

迭代解法：

聲明三個指針，prev = nil, current = head, next = nil,
循環遍歷 LinkedList
1. 改變 next 前，先保存 next，設置 next = current.next
2. 然後改變 next，這一步是反轉的關鍵，設置 current.next = prev
3. 然後 prev 和 current 向下個節點移動，設置 prev = current, current = next

代碼如下：


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var mutHead = head
        if mutHead == nil || mutHead?.next == nil {
            return mutHead
        }
        
        // initialize three pointers 
        // prev as NULL, curr as head, next as NULL
        var prev: ListNode?
        var curr = head
        var next: ListNode?
        
        // iterate through the link list, in the loop do the following
        while (curr != nil) {
            // Before changing next of current
            // store the next node
            next = curr?.next
            
            // Now change next of current
            // This is where revering happens
            curr?.next = prev
            
            // Move the prev and curr one step ahead
            prev = curr
            curr = next
        }
        
        return prev
    }
}

解法三#

遞歸解法：另一種不同的理解，Reverse Linked List

重要的是改變 next 指針指向，而不是賦不同的值。

聲明兩個 ListNode，prev 和 temp。
prev 用於代表前一個，temp 代表暫時存儲的，加上 mutHead 當前的，一共還是三個 ListNode。
循環，mutHead 不為空，
1. temp = mutHead，把 temp 賦值為當前。
2. mutHead = mutHead.next，把 mutHead 賦值為下一個。
3. temp.next = prev，把 temp 的 next 指向 prev，注意此時 temp 的值是當前，即當前的下一個是 prev，指針的方向就實現了反過來。
4. prev = temp，把 prev 賦值為 temp，即 prev 賦值為當前，然後繼續下一次遍歷，直到 mutHead 為空停止。

代碼如下：


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var mutHead = head
        if mutHead == nil || mutHead?.next == nil {
            return mutHead
        }
        
        var prev: ListNode?
        var temp: ListNode?
        while (mutHead != nil) {
            temp = mutHead
            mutHead = mutHead?.next
            temp?.next = prev
            prev = temp
        }

        return prev
    }
    
}

解法四#

遞歸解法，參考 reclusive reverse linked list，
主要需要理解：
遞歸中每一步賦值 curr.next.next = curr 和 curr.next = nil 兩步。


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var mutHead = head
        if mutHead == nil || mutHead?.next == nil {
            return mutHead
        }
        
        // 递归
        let newHead = reverseList(mutHead?.next)
        
        // 下面代碼要分開看
        // mutHead?.next指的是 mutHead 的下一个 ListNode
        // mutHead?.next?.next指的是 mutHead 的下一个 ListNode 的 next 指向
        // 這樣就完成了 reverse指向
        mutHead?.next?.next = mutHead
        // 然後把 mutHead?.next 即 mutHeead 的 next 指向清除
        mutHead?.next = nil

        return newHead
    }
}