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

Reverse linked lists

The title

Given the head node of a single 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: []

 

Tip:

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

Advanced: Lists can be reversed iteratively or recursively. Can you solve the problem in two ways?

Answer key

Ask questions

  • How do I keep the next node of a linked list node from being lost during inversion?

Analysis of the iteration

  • First define three Pointers intopre,cur,nextAnd initialize the pointer
  • prePoint to thenull.curPointing to the head node,nextPoint to thecurThe next node of the node pointed to

  • willcurThe node to which the pointer points pointspreThe node pointed to

  • mobilepretocurThe position of

  • mobilecurtonextThe position of

  • At this point, the first node has been reversed and willnextPointer tocurThe next node of the node pointed to.

  • Repeat the preceding steps whencurPointer tonull“Indicates that the inversion of the entire list is completed.

Conclusion the iteration

  • Initialize the sentinel nodeprefornull.curIs the current nodehead
  • Start the loop, recordnextIs the next node of the current node
  • Check whether the current node isnull
  • Exchange, respectively,pre,cur,nextMake its reverse
  • The loop is broken when cur is null

Code implementation iteration

/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
    if(! head)return null
    var pre=null
    var cur = head
    while(cur){
        const next = cur.next;
        cur.next = pre;
        pre = cur
        cur=next
    }
    return pre
};
Copy the code

Code optimization iteration

Code optimization by using ES6 destruct assignment

/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
    if(! head)return null
    var pre=null
    var cur = head
    while(cur){
        [cur.next,pre,cur] = [pre,cur,cur.next]
    }
    return pre
};
Copy the code

Analysis of the recursive

  • The list initialization state, which is recursive, can be reversed from the last bit back

  • Since the last node points to the next node is empty and there is no next node, the current node is returned.

  • Analyze the current node from the penultimate nodeheadThe next node, the next nodehead.nextPoint to the current nodehead, points the current node tonull.

Repeat execution…

Eventually the whole list is reversed

Conclusion the recursive

  • First of all defineprePointer to the node after the next node of the current node is reversed
  • Because I’m going to need it laterheadThe current node andhead.nextUse requires judgmentheadWhether the current node isnull,head.nextWhether there is.
  • I keep recursing over and over again,head.nextThe next node points to the current node and disconnects the current node from the next node, that is, becomesnull.

The code implements recursion

/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
    if(! head || ! head.next)return head
    let pre = reverseList(head.next)
    head.next.next = head
    head.next = null
    return pre
};
Copy the code