merging two sorted linked lists into one linked list in python

Question

here is my code:

def merge_lists(head1, head2):
    if head1 is None and head2 is None:
        return None
    if head1 is None:
        return head2
    if head2 is None:
        return head1
    if head1.value < head2.value:
        temp = head1
    else:
        temp = head2
    while head1 != None and head2 != None:
        if head1.value < head2.value:
            temp.next = head1
            head1 = head1.next
        else:
            temp.next = head2
            head2 = head2.next
    if head1 is None:
        temp.next = head2
    else:
        temp.next = head1
    return temp
    pass

the problem here is stucked in the infinite loop.can any one tell me what the problem is

the examples are:

 assert [] == merge_lists([],[])
 assert [1,2,3] == merge_lists([1,2,3], [])
 assert [1,2,3] == merge_lists([], [1,2,3])
 assert [1,1,2,2,3,3,4,5] == merge_lists([1,2,3], [1,2,3,4,5])

Solution 1

The problem with the current code is that it causes a side-effect of the temp node's next before it navigates to the next node from the current node. This is problematic when the current temp node is the current node.

That is, imagine this case:

temp = N
temp.next = N  # which means N.next = N
N = N.next     # but from above N = (N.next = N) -> N = N

There is a corrected version, with some other updates:

def merge_lists(head1, head2):
    if head1 is None:
        return head2
    if head2 is None:
        return head1

    # create dummy node to avoid additional checks in loop
    s = t = node() 
    while not (head1 is None or head2 is None):
        if head1.value < head2.value:
            # remember current low-node
            c = head1
            # follow ->next
            head1 = head1.next
        else:
            # remember current low-node
            c = head2
            # follow ->next
            head2 = head2.next

        # only mutate the node AFTER we have followed ->next
        t.next = c          
        # and make sure we also advance the temp
        t = t.next

    t.next = head1 or head2

    # return tail of dummy node
    return s.next

Solution 2

Recursive algorithm for merging two sorted linked lists

def merge_lists(h1, h2):
    if h1 is None:
        return h2
    if h2 is None:
        return h1

    if (h1.value < h2.value):
        h1.next = merge_lists(h1.next, h2)
        return h1
    else:
        h2.next = merge_lists(h2.next, h1)
        return h2

Comments

[srik sri]

thanks for telling me i understood the concept and code well.thanks

[Shruti Kar]

Can you specify the time and space complexity of this solution?

[WaLinke]

Hi and thanks for your feedback. However, explaining how this can solve the OP question and why his solution didn't work is more valuable.

[Aditya K Prasad]

@WaLinke Thanks for pointing out, I have updated the solution of merging two linked list with explanation.

[lifelonglearner]

Can you explain the dummy node concept? I did indeed have many more lines and control flow.

[drmuelr]

Welcome to Stack Overflow! Thanks for providing this algorithm along with its time and space complexity. Can you explain how it works? Why have a Solution class instead of just having a mergeTwoLists function? What's the difference between head and res, and why do they both refer to the same object?

[Rakshit Ajay]

Actually let me make clear, it is the problem of the leet code as I mentioned so here I was just trying to answer the problem, the logic itself.

[Rakshit Ajay]

#create a new linkedlist which is used to store the result #here I have used two refereces to the same list since I should return the root of the list #head will be used during the process and res will be returned.

[Rakshit Ajay]

I hope you get it.

[drmuelr]

Thanks for responding! Since you have added details about your own answer, you should edit your answer to include those details. (You can always edit your own posts.) They will be much easier to read compared to having them in comments.

[Rakshit Ajay]

Ok, I wil do that.