Need an explanation to a Recursive reversed singly linked list code in javascript

Question

I've console.log every line, saw many youtube videos about, but can't wrap my head around it. I need a step by step of what's going on.

To give an example, I understand that return head after the if-statement never gets called, but it should considering that every time that newHead gets declared it calls head.next as the new head in reverseList(head), which should lead to head.next === null.

Below is my code:

let headList = {
  value: 1,
  next: {
    value:2,
    next: {
      value:3,
      next: {
        value:4,
        next: {
          value:5,
          next: null
        }
      }
    }
  }
}

function reverseList(head) {
    if(head == null || head.next == null) {
        return head
    }

    newHead = reverseList(head.next);

    head.next.next = head;
    
    head.next = null;
    return newHead;

};

reverseList(headList)

Answer 1

return head after the if statement actually does get executed.

In your function body, we almost immediately call it back recursively, so it is like climbing ladder, executing first part of function :

    if(head == null || head.next == null) {
        return head
    }

    newHead = reverseList(head.next);```

For each of our heads:

Head 1 ↩
  Head 2 ↩
    Head 3 ↩
      Head 4 ↩

Now we are at Head 4 and again recursively call function with argument { value: 5, next: null }, but this is the last time we are performing recursion, because we reach function's base case - function argument satisfies if statement, and it returns to Head 4 immediately.

Now we will climb back down this call stack and execute second part of the function for each head on the way down.

 // newHead = reverseList(head.next); <-- Resuming from here on the way back

    head.next.next = head;
    
    head.next = null;
    return newHead;

FREEZE THE TIME now, while we are at Head 4, preparing to climb down the call stack!

Since we passed head.next as the argument to the last recursive function call and got it back unchanged, head.next and newHead is pointing at exactly the same object.

And remember, we are in Head 4 now, so head.next.next = head is the same as newHead.next = head. This means Head 4 comes after Head 5 now! Function returns { value: 5, next: { value: 4, next: null }}.

Let's continue execution and now we are in Head 3.

The reason why we need to write head.next.next instead of newHead.next is because on the way down the call stack we need to attach Head 3 object to Head 4.next property and not newHead.next (since newHead.next already points to Head 4).

head.next.next is like saying 'i want to be in front of the head which was in front of me when we started executing function.

Since Head 3.next references Head 4, head.next.next will put Head 3 in Head 4.next property and that is all we need.

So on the way down Head 4 becomes Head 5.next, Head 3 becomes Head 4.next etc.

Recursive functions can be hard to grasp intuitively so i recommend starting from easier ones, for example here: Recursion in JavaScript Explained Using a freeCodeCamp Challenge.