A: hi! ~ Hello, everyone, I am YK bacteria 🐷, a front-end microsystem ✨, like to share their small knowledge 🏹, welcome to follow me 😘 ~ [wechat account: YK2012YK2012, wechat official account: ykyk2012]

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

Today we’re going to do a very classic and very high frequency problem, reverse linked lists. We’re going to solve this problem recursively and non-recursively, but the recursion is a little bit harder to understand, and it’s going to help us understand the idea of recursion

206. Reverse linked lists

Given the head node of a single linked list, reverse the list and return the reversed list.

【 solution 1 】 Non-recursive

Here is an inverted list is not an inverted array, so we can directly modify the pointer between the nodes to achieve the operation of the inverted list!

Take a linked list as an example: 3 -> 2 -> 1, we first reverse the pointer relationship of the first two nodes to get 3 < -2 -> 1, then we reverse the pointer behind to get 3 < -2 < -1, then we reverse the linked list, the sequence of traversal is 1 -> 2 -> 3

  1. Initialize the
let prev = null;
let curr = head;
Copy the code

So now we just need to focus on how do we change the pointer between the two nodes

  1. Pointer to reverse
let temp = curr.next;
curr.next = prev;
Copy the code

  1. Ward pointer
prev = curr;
curr = temp;
Copy the code

  1. One time result

Loop over and reverse all Pointers

var reverseList = function(head) {
    let prev = null;
    let curr = head;
    while (curr) {
        let temp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = temp;
    }
    return prev;
};
Copy the code

I’m going to show you with a GIF that’s the GIF link

Finally, let’s look at the results

【 solution 2 】 Recursion

Let’s think about it this way, a linked list, if at some point, everything at the back has been reversed, what does the front do

Use recursion way to solve the problem, recursion from the beginning node to the end, recursion exit is the last node. The last node serves as the head node after the inversion.

The next step is to invert each level of recursion, as shown in the following GIF

Dynamic figure link

var reverseList = function(head) {
    // Recursive exit returns the last node as the inverted header
    if (head == null || head.next == null) {
        return head;
    }
    
    // the newHead newHead points to the tail, and the recursion will not return until the end is traversed
    const newHead = reverseList(head.next);
    
    // At each level, the next node of head points to itself.
    head.next.next = head;
    // head points to null. In order to achieve the purpose of reversal.
    head.next = null;
    
    return newHead;
};
Copy the code

Finally, please pay attention to my column and make good friends with YK bacteria