Interview challenge · easy · linked-list, recursion

Merge Two Sorted Lists

The challenge

Given the heads of two sorted linked lists, merge them into one sorted list made by splicing together the nodes of the two lists. Return its head.

Example

list1 = 1 -> 2 -> 4
list2 = 1 -> 3 -> 4
         ->  1 -> 1 -> 2 -> 3 -> 4 -> 4

Idea: a dummy head and a tail pointer. Keep taking the smaller of the two current nodes and append it to the tail; when one list runs out, attach the rest of the other. Time O(n + m), space O(1).

The solution

1# Merge Two Sorted Lists - ayotl.dev
2class Node:
3    def __init__(self, val, next=None):
4        self.val, self.next = val, next
5
6
7def merge(a, b):
8    # dummy head: no special case for 1st
9    head = tail = Node(0)
10    while a and b:
11        # take the smaller node, advance it
12        if a.val <= b.val:
13            tail.next, a = a, a.next
14        else:
15            tail.next, b = b, b.next
16        tail = tail.next
17    tail.next = a or b  # append leftovers
18    return head.next
19
20
21def build(vals):
22    head = None
23    for v in reversed(vals):
24        head = Node(v, head)
25    return head
26
27
28n = merge(build([1, 2, 4]),
29          build([1, 3, 4]))
30out = []
31while n:
32    out.append(str(n.val))
33    n = n.next
34print(" -> ".join(out))

$ python3 merge_two_sorted_lists.py

1 -> 1 -> 2 -> 3 -> 4 -> 4

The video

Watch on YouTube →