Wie rekursive Form von Reinigungsduplikate in eine verkettete Liste einfügen?

Question

Diese Funktion „reinigt“ Duplikate aus einer Liste

verknüpft wie

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 

Wie würde die rekursive Art und Weise für diese Funktion aussehen?

Answer 1

Die einfachste Lösung wäre, Ihre While-Schleife in Tail-Recursion zu verwandeln, aber das ist nicht das, was Sie wollen.

Ich nehme an, dass diese Selbst-Sache mit _front und _count eine zusätzliche Struktur ist, die die Liste "hält" - wir können sie entweder weiterleiten (wie unten), oder die Listenmitglieder danach neu zählen. Es könnte wie folgt aussehen:

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) 

Beachten Sie, dass jetzt nur Sie haben, würden den letzten (WRT zur Liste der Links) Auftreten von jedem Wert, so dass Sie danach die Liste umkehren mögen.

Ab Wieder Zählen der neuen „aufgeräumte“ -Liste, können Sie es mit einem anderen rekursive Funktion tun könnte:

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

Mit freundlichen Grüßen!

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 

Rufen Sie einfach an self.clean_recursive(), um ins Rollen, das Argument nur für die Rekursion verwendet wird.