how do we organise a linked-list recurrence relation to merge two sorted linked list?

I have edited the code to incorporate the notes from below (from Trincot), the only thing I am still not clear about is the “l1.next= MergeTwoLists(l1.next,l2)” ; I still don’t think this is right- any ideas how to amend this?

Also, do I need a while statement, since the recursive call seems to loop in some sense already.

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]


def MergeTwoLists(l1,l2):
    prehead = ListNode(-1)
    pointer_run = prehead

    #Base Case
    if not l1:
        return l2
    if not l2:
        return l1


    #Recurrence Relation
    while l1 or l2: 
        if l1.val < l2.val:
            pointer_run.next = l1
            l1_temp = l1.val
            l1.next= MergeTwoLists(l1.next,l2)

        else:
            pointer_run.next = l2
            l2.next = MergeTwoLists(l1,l2.next)


    return prehead.next

Answer

I am getting None as the output.

This happens when l2.val == l1.val. This is a case that is not captured by any if in your code, and so prehead.next is executed. But that next attribute never received a value other than the initial value, which I suppose is set to None by the ListNode constructor.

There are the following issues:

• The last if should really be an else, as you want to capture the above described case in one of those two blocks. As both these blocks (the if block and now else block) end with a return, there should be no possibility to ever get to return prehead.next: that statement can be removed. That also means that prehead is never read after its next attribute is assigned a value, and therefore serves no purpose.

• return MergeTwoLists(l1.next,l2) is not correct. You need to assign the returned value to l1.next. And to avoid that you mutate the input lists, you should first make a new node with the value at l1 and assign to that new node’s next attribute. The same is true for the mirrored situation.

• The first base case is not necessary, as it is covered by the next.

As ListNode was not given, I add the definition that I will use in the corrected code:

class ListNode:
    # Constructor allows caller to optionally provide a next node
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

    # A method to ease the iteration of all list values
    def values(self):
        yield self.val
        if self.next:
            yield from self.next.values()

    # Define the representation of a list (e.g. for printing)
    def __repr__(self):
        return " → ".join(map(repr, self.values()))

    # A class method to ease the creation of a list
    @classmethod
    def fromvalues(cls, *values):
        head = None
        for val in reversed(values):
            head = cls(val, head)
        return head

Here is the corrected function:

def MergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val < l2.val:
        return ListNode(l1.val, MergeTwoLists(l1.next, l2))
    else:
        return ListNode(l2.val, MergeTwoLists(l1, l2.next))

Here is how you can run it:

l1 = ListNode.fromvalues(1, 2, 4) 
l2 = ListNode.fromvalues(1, 3, 4)
result = MergeTwoLists(l1, l2)
print(result)  # 1 → 1 → 2 → 3 → 4 → 4