Linked Lists

# crosscompute

# merge two sorted singly linked lists so that the merged list is still sorted

# naive approach: traverse each list
# grab the min and link to new list
def merge_lists(L1, L2):
    dummy_head = tail = Node(...)
    node1 = L1.head
    node2 = L2.head
    while node1 and node2: # lists not empty
        if node1.data <= node2.data:
            tail.next = node1 # attach node1 to tail of new list
            node1 = node1.next # stepping node1 pointer to the next node on L1
        else:
            tail.next = node2
            node2 = node2.next
        tail = tail.next
    tail.next = node1 or node2 # takes the leftover : take tail of one of the lists and link to new list
    result = LinkedList()
    result.head = dummy_head.next
    return result

# O(n) of number of items in new list created
# fundamental v. critical complexity?