I am trying to understand how recursion works in the following code for merging two sorted linked lists
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// Base cases
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
// Recursive case
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}
I am struggling to visualize how the recursive calls are connecting the nodes of list1 and list2 during the merge process specially
thank you in advanced
Assume you have two lists like shown in the following image:
The node list1
is the start of one list and list2
is the start of another list. The comparing if()
block decides which next node should be returned (return list1;
or return list2;
) from the current mergeTwoLists()
method call. The recursive method call
mergeTwoLists(list1.next, list2);
or
mergeTwoLists(list1, list2.next);
will calculate what would be the next node after that current one. Notice how in the two mergeTwoLists()
method calls, one argument is the same start point but the other argument is the following node of the other start node. When the list1.next
reference or list2.next
reference will be passed to the recursive method call, the original node list1
or list2
becomes "free". In fact, it will be reused as a new node in your resulting merged list. For this "free" node, the .next
field has to be set to the next node in line. That is what the line
list1.next = mergeTwoLists(...
or
list2.next = mergeTwoLists(...
is doing.
So the code block with the recursion part will do three things (assume that list1.val
is less than list2.val
, but it's the same other way around):
mergeTwoLists(list1.next, list2);
(this will "free up" the node list1
). A node is returned by that method.list1.next
field (keep in mind that list1.val
hasn't been changed or lost)return list1;
)Check the following image to visualize the situation:
Here you see where one node has been "cut-off" and the blue area will calculate the remaining merged list with the new start points list1.next
and list2
.
The if()
block will decide which node to "cut-off" and what the remaining result will be. A snapshot of your progress might look like this:
Here you see that the nodes has been cut-off from either list1
or list2
and add to the resulting merged list (red area) with the corresponding source code list1.next = ...
or list2.next = ...
.
At some point you reach the recursive base cases where one list is NULL
, so you return either list1
or list2
directly (no need to cut-off any more nodes, they would have been put together in the same order anyway).