We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Merge two sorted linked lists
  2. Discussions

Merge two sorted linked lists

  • aditaima2004
     + 0 comments

    This is my solution using Python3. This solution is inspired by the technique used in mergesort to combine 2 sorted lists.

    def mergeLists(head1, head2):
    # Checking if any linkedlist is empty
    if not head1:
        return head2
    elif not head2:
        return head1
    # This is executed if both lists exist
    if head1.data<=head2.data:
        headmerged=head1
        head1=head1.next
    else:
        headmerged=head2
        head2=head2.next
    prevnode=headmerged
    while head1 and head2:
        if head1.data<=head2.data:
            prevnode.next=head1
            head1=head1.next
        else:
            prevnode.next=head2
            head2=head2.next
        prevnode=prevnode.next
    # One of the lists is exhausted
    # The remaining part of the other list is appended at end
    if not head1:
        prevnode.next=head2
    else:
        prevnode.next=head1
    return headmerged