Write a function in Python that returns (not mutates!) a new linked list that contains all elements in linked list
def duplicate(lnk, times): """ >>> link = Link(1, Link(2, Link(3))) >>> duplicate(lnk, 2) Link(1, Link(1, Link(2, Link(2, Link(3, Link(3)))))) """ # Your Code Here
def duplicate(lnk, times): if lnk is Link.empty: return Link.empty else: result = duplicate(lnk.rest, times) for _ in range(times): result = Link(lnk.first, result) return result
First and foremost, we want to set up our base case. If we've recursed to the end of
lnk, we should just return
Link.empty since we want to finish off the list that we're returning. Furthermore, if
lnk is parsed in as simply an empty list, we should return that since there are no elements to duplicate.
Other than that, we can start from the end
lnk and work our way up. We create a new linked list to be returned,
result, and call
duplicate on it to turn it into a duplicated linked list (the recursive leap of faith comes in handy here). Once that's done for the current element, we actually want to duplicate the element - so therefore we utilize a for loop and attach
lnk.first to the front
Once that's done, we can safetly return
result, and when we reach the end of the recursion chain,
result is what we get.
Now that you're done with this problem, if you'd like a challenge, try writing this completely recursively (ie, without the for loop!)