从链表 Python 中删除重复项 [英] Remove Duplicates from Linked List Python

问题描述

我正在运行以下代码以从链接列表中删除重复项.但是我的代码只在删除重复项之前打印链表.一旦调用 removeDup 方法，它就不会打印任何内容.下面是我的代码.请告诉我我错过了什么.

I am running below code to remove duplicates from Linked List. But my code only prints linked List before removing duplicates. Once removeDup method is called, it does not print anything. Below is my code. Please tell me what am I missing.

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.next is not None:
            if second.data == current.data:
                current.next = current.next.next
            else:
                current=current.next


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()

推荐答案

您删除发现的重复项的逻辑不正确.它会导致您删除值第一次出现和最后一次出现之后的点之间的所有项目.对于您的示例列表，这会导致一个项目，14 在重复数据删除运行后打印(它从第一个值之后到最后一个值，尽管它也在此过程中进行了一些较小的剪切).

Your logic for removing the duplicated items you find is not right. It causes you to cut out all the items between the first occurrence of a value and a point past its last occurrence. For your example list, that results in a single item, 14 being printed after the deduplication runs (it cuts from just after the first value to the end, though it makes some smaller cuts along the way too).

这是您的 removeDups 方法的固定版本.

Here's a fixed version of your removeDups method.

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 子句.

The main change is that second points to the node before the second node we're actually interested in checking. We do all our work on second.next. We need to keep the reference to second so we can easily cut second.next out of the list. Doing it this way requires that we don't advance second if we've cut out a node, so the second = second.next line needs to be in an else clause.

由于 current 和 second 在每次更新到 current 后总是以相同的值开始，我改变了逻辑以将它们分配给一个声明.原来的方式会很好用，我只是觉得这种方式更好看.

Since current and second always start with the same value after each update to current, I changed the logic to assign both of them in a single statement. It would work fine the original way, I just think this way looks nicer.

这篇关于从链表 Python 中删除重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！