CODEWITHSUNDEEP
javaalgorithmrecursion
Aedgen
Aedgen

Reputation: 11

How does this recursion and back tracking work in LeetCode?

This function which will print the nodes of a linked list in reverse: 

void recur(ListNode head) {
    if(head == null) return; 
    recur(head.next);
    tmp.add(head.val);
}

If the list is 1 -> 2 -> 3 then tmp (an ArrayList) will add the value of the node.

At last, we can get a list [3, 2, 1] via printing tmp. However, I do not know why it works. Why does the recur function loop to the last node then add the values in reverse order?

Upvotes: 0

Views: 80

Answers (2)

ish
ish

Reputation: 171

It's pretty much simple, let's consider the [1 -> 2] node with two ListNode and we want to reverse with you function:

void recur(ListNode head) {
    if (head == null) return;
    recur(head.next);
    tmp.add(head.val);
}
  1. On the first stem, the head will point to 1 value, this check if (head == null) will return false since head node is not null.
  2. Then we call the same function recur but for the next node with value 2, and execution of recur start over but with node 2 as a head node. We again check if (head == null) -> false, same reason, head is not null here.
  3. Then we call the same function recur but for the next node which is null head.next -> null, since there are no nodes anymore after node 2. We check if (head == null), but now we have true, the current node, meaning there are no nodes left after and we can't go further calling recur() again. So, we stop the recursion with a return statement.
  4. Now, we return again to step #2 and continue execution, because the execution of recur(head.next) ends by return statement. That means, this node is the last one, and we put its value to the tmp. And the execution of recur for ListNode 2 ends, since there are no code lines after.
  5. Now, we return again to step #1 and do the same logic as described in step 4. Since recur for node 2 ends its execution we proceed and put value 1 to tmp array.

if (head == null) return; - this check, called recursion base case, meaning when we need to end execution and exit?, without it recursion will go infinitely.

We dig to the end of the ListNode and then return again to the top. To be able to put ListNode value to the tmp we need first put next value to the tmp and so on.

I hope, I explained more accurately and its more clear for you now.

Upvotes: 0

Joby Wilson Mathews
Joby Wilson Mathews

Reputation: 11126

I think this flow diagram may help you.

enter image description here

As you can see from the diagram the head.value is added to the tmp list only when end of the linked list is reached. i.e . head becames null

Upvotes: 1

Related Questions