当前位置:网站首页>Algorithem_ReverseLinkedList

Algorithem_ReverseLinkedList

2022-04-23 14:06:00 莫空9081

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

<!--more-->

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

Example 1:

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

Example 2:

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

Example 3:

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,页面最下方的视频,多看几遍。

迭代解法:

  1. 声明三个指针,prev = nil, current = head, next = nil,
  2. 循环遍历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指针指向,而不是赋不同的值

  1. 声明两个ListNode,prev 和 temp
  2. prev 用于代表前一个,temp 代表暂时存储的,加上 mutHead 当前的,一共还是三个 ListNode
  3. 循环,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
    }
}

版权声明
本文为[莫空9081]所创,转载请带上原文链接,感谢
https://cloud.tencent.com/developer/article/1986108