Exercise 3 solution

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

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

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

    def merge_sorted(a, b):
        dummy = Node(None)
        tail = dummy
        while a and b:
            if a.value <= b.value:
                tail.next, a = a, a.next
            else:
                tail.next, b = b, b.next
            tail = tail.next
        tail.next = a or b
        return dummy.next

    print(to_list(merge_sorted(build([1, 4, 6]), build([2, 3, 7, 9]))))
    print(to_list(merge_sorted(build([]), build([5]))))
    print(to_list(merge_sorted(build([1, 1]), build([1]))))

Output:
    [1, 2, 3, 4, 6, 7, 9]
    [5]
    [1, 1, 1]

The dummy node removes the "is the result still empty?" special case:
tail always has a node to attach to, and dummy.next is the real head. No
new nodes are created; the existing ones are relinked, which is the thing
linked lists do cheaply. When one list runs out, the rest of the other is
attached in one step. Using "<=" keeps the merge stable (equal values from
the first list stay first).