这段代码处理从Python中的链表中删除重复项。问题似乎出在remove功能上。
class Node(object):
def __init__(self, data = None, next_node = None):
self.next_node = next_node
self.data = data
#get data at that location
def get_data(self):
return self.data
#get next element in linked list
def get_next(self):
return self.next_node
#point to node specified by argument
def set_next(self, new_next):
self.next_node = new_next
class LinkedList(object):
def __init__(self, head = None):
self.head = head
#insert element in linked list
def insert(self, data):
new_node = Node(data)
new_node.set_next(self.head)
self.head = new_node
#remove duplicates
def remove(self):
#point to head
current = self.head
previous = None
removed = False
#variable to compare the current data with the rest
new = current
new = new.get_next()
#while current is not None
while current:
if current.get_data() != new.get_data():
previous = new
new = new.get_next()
#if same data, delete extra node from list
else:
removed = True
#if only one element in list
if previous is None:
self.head = new.get_next()
else:
previous.set_next(new.get_next())
new = new.get_next()
#if 'new' reaches end of list, do this
if new is None:
current = current.get_next()
previous = current
new = current
new = new.get_next()
if not removed:
print("No duplicates!")
#print resulting linked list
def print_result(self):
current = self.head
while current:
print(current.get_data(), end = " ")
current = current.get_next()
(我忽略了代码的"函数调用"部分(。
我在while current:(在remove函数中(后的第一个if语句中收到一个属性错误，说：
Traceback (most recent call last):
File "python", line 64, in <module>
File "python", line 26, in remove
AttributeError: 'NoneType' object has no attribute 'get_data'
我不明白哪个是None，为什么。任何帮助将不胜感激！
假设您可以接受指数级运行时间，您的一般方法似乎是正确的，但有一些细节会导致崩溃。以下是我随手发现的几个：
-
如果列表长度为 1，
if current.get_data() != new.get_data():将崩溃，因为newNone。 -
这些行：
current = current.get_next() previous = current new = current new = new.get_next() # boom!当您到达列表末尾时会崩溃。
current是最后一个节点，您得到下一个节点，即None，然后尝试None.get_next()。
要解决这些问题，请一次一个节点地浏览列表，并在每次next时检查None以避免崩溃。取消链接也是如此：一次只取消一个节点的链接，方法是将prev保留在原处并将prev.next_node和curr设置为curr.next，然后在执行其他任何操作之前测试curr是否None。
这是一个简单的工作版本：
def remove(self):
curr = self.head
while curr:
runner = curr.next_node
prev = curr
while runner:
if runner.data == curr.data:
prev.next_node = runner.next_node
else:
prev = runner
runner = runner.next_node
curr = curr.next_node
这个想法是使用curr逐个节点逐步浏览列表。对于每个节点，创建一个runner和prev，它将逐个节点循环访问列表节点的其余部分，并取消与curr匹配的任何节点的链接。
还有一种使用set(以空间换取速度(的线性方法：
def remove_linear(self):
seen = set()
curr = self.head
prev = None
while curr:
if curr.data not in seen:
seen.add(curr.data)
prev = curr
else:
prev.next_node = curr.next_node
curr = curr.next_node
试试吧！
最后一点：Python 通常不使用 getter 和 setter;它们增加了冗长性并且不提供任何真正的保护，所以我在上面的代码中省略了它们。信任客户端，并对"私有"变量使用下划线前缀。