從鏈接列表中刪除重複項Python

Question

我在下面的代碼中運行以從鏈接列表中刪除重複項。但是我的代碼在刪除重複項之前僅打印鏈接列表。一旦調用removeDup方法，它不會打印任何東西。以下是我的代碼。請告訴我我錯過了什麼。

class Node: 
    def __init__(self, data): 
     self.data = data 
     self.next = None 

class LinkedList: 
    def __init__(self): 
     self.head = None 

    def insert(self, data): 
     node = Node(data) 
     node.next=self.head 
     self.head = node 

    def printl(self): 
     current = self.head 
     while current: 
      print current.data 
      current= current.next 

    def removeDups(self): 
     current = self.head 
     while current is not None: 
      second = current.next 
      while second: 
       if second.data == current.data: 
        current.next = second.next.next 

       second = second.next 
      current = current.next 
#  l.printl() 


l= LinkedList() 
l.insert(15) 
l.insert(14) 
l.insert(16) 
l.insert(15) 
l.insert(15) 
l.insert(14) 
l.insert(18) 
l.insert(159) 
l.insert(12) 
l.insert(10) 
l.insert(15) 
l.insert(14) 

l.printl() 
print "===============" 

l.removeDups() 
l.printl() 

Answer 1

您刪除重複項目的邏輯是不正確的。它會導致您刪除第一次出現的值和最後一次出現的點之間的所有項目。對於您的示例列表，在重複數據刪除運行後會打印一個單獨的項目14（從第一個值到最後一個值之間切換，儘管它在此過程中也會進行一些較小的削減）。

這是您的removeDups方法的固定版本。

def removeDups(self): 
    current = second = self.head 
    while current is not None: 
     while second.next is not None: # check second.next here rather than second 
      if second.next.data == current.data: # check second.next.data, not second.data 
       second.next = second.next.next # cut second.next out of the list 
      else: 
       second = second.next # put this line in an else, to avoid skipping items 
     current = second = current.next 

主要變化是second指向節點前的第二個節點，我們實際上感興趣的檢查。我們在second.next上做了我們所有的工作。我們需要保留對second的引用，以便我們可以輕鬆地將second.next從列表中刪除。這樣做需要我們不提前second，如果我們已經刪除了一個節點，所以second = second.next行需要在else條款。

由於current和second在每次更新到current後總是以相同的值開始，所以我改變了在單個語句中分配它們兩者的邏輯。它可以很好地工作，我認爲這種方式看起來更好。