Linked Lists: Difficult Solutions

VIsualizing linked lists

Draw lnk after the call to secret.

lst = Link(1, Link(2, Link(3, Link(4))))
def secret(lst):
    if lst is Link.empty or lst.rest is Link.empty:
        return lst
    else:
        x = lst.rest
        y = secret(lst.rest.rest)
        x.rest = lst
        lst.rest = y
        return x
lnk = secret(lst)

Screen Shot 2019-08-26 at 6.30.59 PM.png

code writing

Write out a function that will take in two sorted linked lists and combine them into one sorted linked list (assume there are no duplicate values).
def merger(lnk1, lnk2):
>>> lnk1 = Link(1, Link(2, Link(5, Link(7))))
>>> lnk2 = Link(3, Link(6, Link(8, Link(9))))
>>> merger(lnk1, lnk2)
Link(1, Link(2, Link(3, Link(5, Link(6, Link(7, Link(8, Link(9))))))))
    if lnk1 is Link.empty:
        return lnk2
    else if lnk2 is Link.empty:
        return lnk1
    else if lnk1.first > lnk2.first:
        return Link(lnk2.first, merger(lnk1, lnk2.rest))
    else:
        return Link(lnk1.first, merger(lnk1.rest, lnk2))