CODEWITHSUNDEEP
pythonrecursion
Patrick Chong
Patrick Chong

Reputation: 157

Why are we returning the head of the TreeNode after each recursive call?

I have a question regarding the trace of the following recursive solution: https://leetcode.com/problems/merge-two-sorted-lists/solution/

It is simply to merge two sorted linked list.

class Solution:
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

Generally, I can follow recursive solutions through, but with ListNodes I am struggling to understand how one connects to another at each recursive call. In particular, why are we returning l1 and l2 after each recursive call? Is this to ensure that we maintain and return the head of the linked list at the end of the function?

I do understand the premise of the solution, which is to compare the heads of the two link lists and connect it with the remainder of the linked list at each stage.

Upvotes: 0

Views: 62

Answers (2)

trincot
trincot

Reputation: 350290

why are we returning l1 and l2 after each recursive call?

First of all, the goal of the function is to return a list, so at least something needs to be returned, in all cases.

I do understand the premise of the solution, which is to compare the heads of the two link lists and connect it with the remainder of the linked list at each stage.

This comparison decides which node will be the head of the list to be returned, so already when we find that l1.val < l2.val, it is clear that l1 must be the head node of the returned list, and so it is expected there will be a return l1.

The recursive call shifts the problem to a situation where the l1 node is not included any more: we already know that l1 will be first, so the problem is reduced by not considering it any more, and solving that smaller problem through recursion. The recursive call will return a list whose first node will be the node that we have to put right after l1. So that is why the recursive result is assigned to l1.next. Note how important it is that the recursive call returns a list (node)!

Upvotes: 1

Zaid Al Shattle
Zaid Al Shattle

Reputation: 1534

More or less, the process here goes as such:

When you use next, you get the next value of the iterator, by returning the variables (l1/l2) you keep that position.

Initially, since the lists are sorted, if you compare between the top items (l1.val,l2.val) you can get the higher value, and extracting the lower one (this output seems to be ascending), you can repeat the process as every time you use next, the value changes.

Returning L1 after next ensures that we do not have repeated values from L1, and reducing the complexity of needing to mess around with indexes and what-not

Eventually, one of the lists will be empty (the first two conditions) and all of the remaining values will be added there.

Upvotes: 0

Related Questions