Merging Sorted Linked Lists

Problem

Given two sorted singly-linked lists, merge the lists

Input

• L1 - pointer to the HEAD of the first linked list
• L2 - pointer to the HEAD of the second linked list

Approach

This algorithm is quite basic but it is a building block to other trickier linked list algorithms.

The most painless and intuitive approach here is to use a dummy node and assign the next pointer of the dummy node to whichever node is smaller -- L1 or L2. Whenever we assign the next pointer, move the corresponding node forward by 1 and move the dummy node by 1.

After the merge, all we need to do is return the dummy node's next pointer, at its initial position.

Solution

def merge_two_sorted_lists(L1, L2):  
    sentinel = tail = ListNode(None)
    while L1 and L2:
        if L1.data < L2.data:
            tail.next, L1 = L1, L1.next
        else:
            tail.next, L2 = L2, L2.next

        tail = tail.next

    remaining = L1 or L2
    if remaining:
        tail.next = remaining

    return sentinel.next