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)
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.