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

  • anw_g01
     + 0 comments

    Using a dummy (temporary) node is neat trick to bypass head pointer management. Just don't forget to skip it when finished by returning head.next:

    def mergeLists(head1, head2):
    # if one LL is empty, return the other
    if head1 is None:
        return head2
    if head2 is None:
        return head1
    new = SinglyLinkedList()        # instantiate a new LL 
    curr = SinglyLinkedListNode(0)  # create dummy node
    new.head = curr                 # start pointer at dummy node
    # traverse both LLs:        
    curr1, curr2 = head1, head2     # pointers for each head
    while True:
        if curr1.data < curr2.data:
            curr.next = curr1
            curr1 = curr1.next
        else:
            curr.next = curr2
            curr2 = curr2.next
        curr = curr.next    # move to next node
        if curr1 is None or curr2 is None:
            break
    # attach the remaining LL:
    if curr1 is not None:
        curr.next = curr1
    if curr2 is not None:
        curr.next = curr2
    return new.head.next    # skip the dummy node