Algorithem_ ReverseLinkedList

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:

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

Example 2:

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?

Solution 1

First of all followup, The most direct solution is , I put LinkNode Converted to an array , Then the array is in reverse order , Regenerate into new LinkNode

The code is as follows ：

/**
 * 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)
    }
}

Solution 2

It's troublesome to understand here , May refer to ,Reverse a linked list, The video at the bottom of the page , Look at it several times. .

Iterative method ：

1. Declare three pointers ,prev = nil, current = head, next = nil,
2. Loop traversal LinkedList
   1. change next front , First save next, Set up next = current.next
   2. Then change next, This step is reverse The key to , Set up current.next = prev
   3. then prev and current Move to the next node , Set up prev = current, current = next

The code is as follows ：

/**
 * 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
    }
}

Solution 3

The recursive method ： A different understanding ,Reverse Linked List

The important thing is to change next Pointer to , Instead of assigning different values

1. Declare two ListNode,prev and temp
2. prev Used to represent the previous ,temp Represents temporarily stored , add mutHead Current , There are still three ListNode
3. loop ,mutHead Not empty ,
   1. temp = mutHead, hold temp Assign to current
   2. mutHead = mutHead.next, hold mutHead Assign to the next
   3. temp.next = prev, hold temp Of next Point to prev, Note that this time temp The value of is current , That is, the current next is prev, The direction of the pointer is reversed
   4. prev = temp, hold prev The assignment is temp, namely prev Assign to current , Then continue the next traversal , know mutHead Empty stop

The code is as follows ：

/**
 * 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
    }
    
}

Method four

The recursive method , Reference resources reclusive reverse linked list,

Mainly need to understand ：

Each step of recursion is assigned a value curr.next.next = curr and curr.next = nil Two steps

/**
 * 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
        }
        
        //  recursive 
        let newHead = reverseList(mutHead?.next)
        
        //  The following code should be viewed separately 
        // mutHead?.next refer to  mutHead  Next  ListNode
        // mutHead?.next?.next refer to  mutHead  Next  ListNode  Of  next  Point to 
        //  That's it  reverse Point to 
        mutHead?.next?.next = mutHead
        //  And then put  mutHead?.next  namely  mutHeead  Of  next  Point to clear 
        mutHead?.next = nil

        return newHead
    }
}