Algorithem_ReverseLinkedList

2022-04-22

Algorithem_ReverseLinkedList

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

解法一

先撇开 followup，最直接的解法时，我把 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，这一步是 reverse 的关键，设置 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
    }
}