“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”

Starting today in nuggets output their own leetcode above the problem records 😁.

The topic is linked here leetcode 206- Reverse linked list

The question

As can be seen from the figure, the title gives a single linked list, and it is necessary to return the linked list after the inversion of the whole list.

Train of thought

An intuitive way to think about it is to move the next pointer of the current node up and down the list to the last node.

For example, invert 1->2->3->4->5-> NULL.

  • First, we define an initial variable pre = null and the iterated variable cur = head, which by default points to head.
  • In the process of backward iteration, since the next pointer of the current node needs to be changed, the variable next=cur.next is used to save the next pointer of the current node in order to prevent the iteration from being terminated due to the release of the next node.
  • Then, the next pointer of the current node points to the previous node, cur.next = pre
  • I’m going to update the pre variable, pre = cur,
  • It then updates the current node to the position of its next node, cur = next.
  • Continue the inversion of the next node…

In this way, the next pointer of each node will point to the pre node after the last inversion in the order of 1, 2, 3, 4 and 5 to complete the inversion of the whole linked list, and the inversion result will be saved in the Pre.

Another, less intuitive way to think about it is to reverse from back to front

Because we need to traverse the list from back to front, it’s natural to think recursively,

  • The recursion starts at the second-to-last node
  • First, point the current node to null
  • Place the next node’s next pointer to the current node and save a reference to the next node
  • Repeat the above steps to complete the reverse of the entire list from back to front

Code implementation

/ / iteration method
var reverseList = head= > {
    if(head == null) return head
    let pre = null,cur = head,next
    while(cur){
        next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    }
    return pre
}
/ / the recursive method
var reverseList = head= > {
    if(head == null || head.next == null) return head
    let p = reverseList(head.next),tail = head.next
    tail.next = head
    head.next = null
    return p
}
Copy the code

conclusion

After the analysis of the reverse linked list, it can be seen that the operation is quite abstract. I think when I am not familiar with the problem, drawing a picture will play a great help.

If you have a better idea of analysis, you are welcome to comment in the comments section! ⛄