算法_反转链表 - 今是昨非

Algorithem_ReverseLinkedList#

给定一个单链表的头节点，反转链表，并返回反转后的链表。

示例 1：

输入: head = [1,2,3,4,5]
输出: [5,4,3,2,1]

示例 2：

输入: head = [1,2]
输出: [2,1]

示例 3：

输入: head = []
输出: []

约束条件：

链表中的节点数在范围 [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
        }
        
        // 初始化三个指针 
        // prev 为 NULL, curr 为 head, next 为 NULL
        var prev: ListNode?
        var curr = head
        var next: ListNode?
        
        // 遍历链表，在循环中执行以下操作
        while (curr != nil) {
            // 在改变当前节点的 next 之前
            // 保存下一个节点
            next = curr?.next
            
            // 现在改变当前节点的 next
            // 这就是反转发生的地方
            curr?.next = prev
            
            // 将 prev 和 curr 向前移动一步
            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 指向
        // 这样就完成了反转指向
        mutHead?.next?.next = mutHead
        // 然后把 mutHead?.next 即 mutHead 的 next 指向清除
        mutHead?.next = nil

        return newHead
    }
}