javarecursionlinked-list

Clarification on Recursion in mergeTwoLists for Linked Lists


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

  1. How does the mergefunction ensure the resulting list is connected properly? and
  2. how do the return values from deeper recursive calls get used to build the final merged list? I’d really appreciate a step-by-step explanation or any tips to understand this process better

thank you in advanced


Solution

  • 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):

    1. Calculate the remaining merged list result by calling mergeTwoLists(list1.next, list2); (this will "free up" the node list1). A node is returned by that method.
    2. Save the result of that recursive method call in the "free" node list1.next field (keep in mind that list1.val hasn't been changed or lost)
    3. Return the "free" node (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).