This is the 9th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Topic Description:

206. Reverse the Linked List (LeetCode) (leetcode-cn.com)

Given the head node of the single linked list, please reverse the list and return the inverted list.

The sample a

Input: head = [1,2,3,4,5]Copy the code

Example 2

Input: head = [1,2]Copy the code

Example 3

Input: head = []Copy the code

Tip:

  • The number of nodes in the list ranges from[0, 5000]
  • -5000 <= Node.val <= 5000

Thought analysis

The iteration

A linked list points to something, and to reverse it, you just point it the other way around.

We simply record the current node, the previous node and the last node, and point the next of the current node to the previous node

  • Defining two Pointerspre 和 cur
  • preThe original pointnullBecause the first node has no previous nodes
  • Each iterationcur 的 nextPoint to thepre

AC code

class Solution {
    fun reverseList(head: ListNode?).: ListNode? {
        var prev: ListNode? = null
        var curr: ListNode? = head
        var next: ListNode? = null
        while(curr ! =null) {
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        }
        return prev
    }
}

Copy the code

recursive

  • I’m going to use a recursive function, and I’m going to recurse all the way to the last node in the list, which is the inverted head node, which I’m going to callprefix
  • After that, every time the function returns, it sets the value of the next nodenextThe pointer points to the current node
  • Let’s make the current nodenextPointer tonullIn order to realize the local inversion from the end of the list
  • When all recursive functions are off the stack, the list reversal is complete.

AC code

class Solution {
    fun reverseList(head: ListNode?).: ListNode? {
        if(null == head || null == head.next){
            return head
        }
        val prefix = reverseList(head.next)
        head.next.next = head
        head.next = null
        return prefix
    }
}
Copy the code

conclusion

The main thing about recursion is that the recursion is not easy to understand, and it’s hard to even look at the code, but to actually understand recursion, you have to draw it on paper. In addition, the video solution of this elder brother is recommended, which is very thorough.

reference

Reverse linked List – Reverse linked list – Force buckle (LeetCode) (leetcode-cn.com)

206. Reverse list – Reverse list – Force button (LeetCode) (leetcode-cn.com)

The Reverse Linked List is Linked by a Linked link (LeetCode) (leetcode-cn.com)

Java/C++ /Python/js animation – reverse linked list – reverse linked list – force button (leetcode-cn.com)

[Reverse linked list] : Double pointer, recursion, demonized double pointer – Reverse linked list – force button (LeetCode) (leetcode-cn.com)