Linked lists · stretch

Merge two sorted linked lists

a and b are sorted linked lists. Write merge_lists(a, b) returning the head of one sorted list made by relinking their nodes — no new Nodes.

A throwaway starting node (a dummy) saves special-casing the first step: build after it, return dummy.next.

right answers
arguments left as they should be
without build

Already written for you — you can use these

1class Node:
2    def __init__(self, value, next=None):
3        self.value = value
4        self.next = next
5 
6def build(values):
7    head = None
8    for v in reversed(values):
9        head = Node(v, head)
10    return head

def merge_lists(a, b):
    values = []
    while a is not None:
        values.append(a.value)
        a = a.next
    while b is not None:
        values.append(b.value)
        b = b.next
    head = None
    for v in reversed(sorted(values)):
        head = Node(v, head)
    return head

Run adds head = head.next after your code, to try it.

Stuck on the idea rather than the code? The Fast and slow, and a dummy head lesson walks through it.