Merge Two Sorted Lists

EasyLinked listLeetCode 21 ↗World 1-7

0:00 / 0:00

Splice two sorted lists into one. Keep a tail pointer behind a dummy head and always take the smaller front node.

▼

The problem

LeetCode 21 (Easy). Given the heads of two sorted linked lists, splice their nodes together into one sorted list and return its head.

Example: list1 = [1,2,4], list2 = [1,3,4] → [1,1,2,3,4,4].

TRY IT ON LEETCODE ▶

The solution

def mergeTwoLists(list1, list2):
    dummy = tail = ListNode()
    while list1 and list2:
        if list1.val <= list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next
    tail.next = list1 or list2
    return dummy.next

Transcript

Merge Two Sorted Lists. You get the heads of two sorted linked lists. Splice their nodes into one sorted list, and return its head.

List one is one, two, four. List two is one, three, four. Merged, that's one, one, two, three, four, four. If either list is empty, the answer is just the other.

The easy way: copy every value into an array, sort it, and build a new list. It works, but sorting costs n log n, it needs extra space, and it ignores that both lists are already sorted.

Instead, zip them together. Start with a dummy node and a tail pointer on it. Compare the two front nodes, attach the smaller one to the tail, and advance that list. When one list runs out, attach the rest of the other.

In code, the loop runs while both lists have nodes. A tie takes from list one. After the loop, the tail takes whatever is left, and we return the node after the dummy.

Let's zip. One and one tie, so list one goes first. Then list two's one. Two beats three. Three beats four. Four and four tie: list one's four. List one is empty, so attach the rest: four.

Each node is attached once, so the time is m plus n, and we only move pointers, so the extra space is constant.

Compare, attach, advance. That's Merge Two Sorted Lists.