Build a Linked ListStep 5 of 5

Merge Two Sorted Lists

12345

Step 5: Merge Two Sorted Lists

Merging two already-sorted lists into one sorted list is the heart of merge sort and a favorite interview question.

Implement merge_two(a, b) where a and b are the heads of two lists sorted in non-decreasing order. Splice the existing nodes together into a single sorted list and return its head. Use a dummy head node so you always have a place to attach the first result.

Either input may be None, and when one list runs out, attach the remainder of the other.

Hints
Starter code
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next


def from_list(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head


def to_list(head):
    out = []
    node = head
    while node is not None:
        out.append(node.value)
        node = node.next
    return out


def reverse(head):
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev


def has_cycle(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


def middle(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow.value


def merge_two(a, b):
    """Merge two sorted lists into one sorted list and return the head."""
    # TODO: use a dummy node and a tail; pick the smaller head each step
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousAll challenges