Summary of link list 206 inverse link list iteration and recursive solution

1. Title Description

Reverse a single linked list. Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULLCopy the code

2. How to solve the problem

  • The iteration

The idea of iteration is simple: flip the list from the beginning, node by node. Each time a node is traversed, the node is broken off the list so that the node pointer points to the reversed part of the list. The code is as follows:

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
    if(! head || ! head.next)return head // If the list is empty, or the list has only one node, it returns directly
    let p = null,z = head,y
    while(z){ // Iterate through the list until the list is null
        y = z // make y point to the head of the list, i.e. store the first node in the y variable
        z = z.next // Make z point to the rest of the list after the u-turn node is removed
        y.next = p // The y pointer to the first node to be removed points to the flipped list
        p = y // Make p point to the head node of the flipped list. That is, p stores the flipped part of the list
    }
    return p
};
Copy the code
  • recursive

The idea of recursion is a little harder to understand. Unlike iteration, recursion starts with the reverse:

5 -> 7 -> 8 -> 4 -> NULL When we recurse to node 4, because the node next points to NULL, we assume that the node belongs to the flipped node and return it directly. 8 -> 4-> NULL = 8 -> next = 8 -> next = null Next =null 4. Next = 8 4->8->null The list behind 7 nodes has been recursively flipped. At this point, we can't think too convoluted. Although the list behind 7 has been flipped to 4->8-> NULL, the next of 7 nodes still points to 8 nodes instead of 4 nodes. Next =null 8. Next = 7 next=null 8. Next = 7Copy the code

The code is as follows:

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
    if(! head || ! head.next)return head
    let tail = head.next,p = reverseList(head.next) // here p always returns the last node of the original list, i.e. the first node of the new list
    head.next = tail.next // tail is the next of the current head, so we point the current head to null
    tail.next = head // Make the current head node pointing to null the last node in the current flipped list
    return p // Return the last node of the original list, i.e. the first node of the new list, so p also stands for the whole list flipped
    
    // The official solution is as follows:
    const p = reverseList(head.next)
    head.next.next = head
    head.next = null
    return p
};
Copy the code

Third, summary

This one, again, is a very simple problem, but the recursion of the list is a little bit convoluted, but the recursion is essentially the same, and it starts at the final bound, which is to flip the list backwards.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign