如何以递归形式清除链表中的重复项

Question

此函数"清除"列表链接中的重复项

def clean (self):
    key_node = self._front
    while key_node is not None:
        # Loop through every node - compare each node with the rest
        previous = key_node
        current = key_node._next
        while current is not None:
            # Always search to the end of the list (may have > 1 duplicate)
            if current._value == key_node._value:
                # Remove the current node by connecting the node before it
                # to the node after it.
                previous._next = current._next
                self._count -= 1
            else:
                previous = current
            # Move to the _next node.
            current = current._next
        # Check for duplicates of the _next remaining node in the list
        key_node = key_node._next
    return

这个函数的递归方式会是什么样子？

Answer 1

最简单的解决方案是将while循环转换为尾部递归，但我想这不是您想要的。

我假设这个带有_front和_count的self-thing是一个"容纳"列表的附加结构——我们可以将其传递(如下所示(，也可以在之后重新计算列表成员。它可能看起来像这样：

    def clean(self)
      self._front = rec_clean(self._front, self)
      return
    def rec_clean(current,self)  
      if current is None:
         return None
         else:
          if member(current._value, current._next):
             self._count -= 1
             return rec_clean(current._next, self)
          else:
             current._next = rec_clean(current._next, self)
             return current
    def member(value, current)
      if current is None:
         return false
         else:
         if current._value == value
            return true
         else:
            return member(value, current._next)

请注意，现在每个值只出现最后一次(wrt到列表的链接(，因此您可能需要在之后反转列表。

在重新计算新的"清理"列表时，您可以使用另一个递归函数：

     def length(current)
       if current is None:
          return 0
          else:
          return 1+length(current._next)

致以最良好的问候！

Answer 2

# ... is just a place holder token that can't be None
# as I can't write what I want, (self, key_node=self._front)
# as self isn't defined at this point!
def clean_recursive(self, key_node=...):
    if key_node is ...:
        key_node = self._front
    elif key_node is None:
        return
    previous = key_node
    current = key_node._next
    while current is not None:
        if current._value == key_node._value:
            # Same situation as when we started, clean
            # rest of list; toss current node & quit loop
            self.clean_recursive(current)
            previous._next = current._next
            self._count -= 1
            break
        previous = current
        current = current._next
    self.clean_recursive(key_node._next)  # check the 2nd, 3rd, etc. element

只需调用self.clean_recurive((即可使其滚动，该参数仅用于递归。