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
Toggle Solution
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!)

results matching ""

    No results matching ""