从链接列表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我更改了逻辑以在单个语句中分配它们.它会以原始的方式工作,我只是认为这种方式看起来更好.