Duplicate Elements
Write a function in Python that returns (not mutates!) a new linked list that contains all elements in linked list lnk
repeated times
times.
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 times
times.
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!)