Back

Explore Courses Blog Tutorials Interview Questions
0 votes
1 view
in Python by (12.7k points)

In python,Can anyone tell me how to merge two sorted linked list into one Linked list?

Look at the below 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 issue here is stucked in the endless loop.can anyone mention to me what the issue is

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])

1 Answer

0 votes
by (26.4k points)

The issue with the current code is that it causes a result of the temp node's next before it explores the following node from the current hub. This is dangerous when the current temp node is the current node.

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

Check the below code for corrected version.

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

Interested to learn python in detail? Come and Join the python course.

Browse Categories

...