Linked Lists

Pay Notebook Creator: Elaine Chan0
Set Container: Numerical CPU with TINY Memory for 10 Minutes 0
In [1]:
# crosscompute
In [2]:
# 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 # attach node1 to tail of new list
            node1 = # stepping node1 pointer to the next node on L1
   = node2
            node2 =
        tail = = node1 or node2 # takes the leftover : take tail of one of the lists and link to new list
    result = LinkedList()
    result.head =
    return result
In [ ]:
# O(n) of number of items in new list created
# fundamental v. critical complexity?