我将一个排序的链表调用到duplicates_sorted方法中，然后它忽略列表中的第一个重复项并打印其余的。为什么它不包括第一个重复？
未排序-1，13，65，78，12，25，1，2，13，39，13，48，10，2
已排序-1、1、2、2、10、12、13、13、25、32、39、48、65，78
打印：2、12、13
我将一个未排序的列表传递给bubble_sort方法并对其进行排序。然后我将该列表传递到deuplicates_sorted方法中。
class Node(object):
item = -1
next = None
def __init__(self, item, next):
self.item = item
self.next = next
def has_next(self):
return self.next!=None
def get_next(self):
return self.next
def set_next(self,node):
self.next=node
class LinkedList(object):
def __init__(self):
self.item=None
self.size=0
def length(self):
curr = self
total = 0
while curr.get_next() is not None:
total +=1
curr = curr.get_next()
return total
def get_next(self):
return self.item.get_next()
def add(self, item):
new_node = Node(item, self.item);
self.item = new_node;
self.size += 1;
def print_list(self):
print("Print List = ", end= "");
if self.item is None:
return;
current = self.item;
print(current.item, end=", ");
while current.get_next():
current = current.get_next();
if not current.has_next():
print(current.item, end="");
else:
print(current.item, end= ", ")
# method that makes problems:
def duplicates_sorted(nums):
k = nums
duplicate_elements = []
while k is not None:
if k.get_next() is None:
break
if k.item == k.get_next().item:
duplicate_elements.append(k.item)
k = k.get_next()
print("Duplicates: ", duplicate_elements)
def bubble_sort(num):
for i in range(num.length()):
m = num.item
n = m.get_next()
while n is not None:
if n.item is None:
break
if m.item > n.item:
swap(m, n)
n = n.next
m = m.get_next()
def swap(node1, node2):
temp = node1.item
node1.item = node2.item
node2.item = temp
def single_list(): #merges two txt files into one
merge_list = LinkedList() #create empty linked list
with open('file1.txt', 'r') as myfile:
for line in myfile:
merge_list.add(int(line.strip()))
myfile.close()
with open('file2.txt', 'r') as myfile:
for line in myfile:
merge_list.add(int(line))
myfile.close
return merge_list
def main():
#creating a linked list
bubble_sortlist = single_list() #prints unsorted list
bubble_sortlist.print_list()
print()
bubble_sort(bubble_sortlist) #prints sorted list
bubble_sortlist.print_list()
print()
duplicates_sorted(bubble_sortlist) #prints duplicates
if __name__ =='__main__':
main()
您混淆了第一个Node和LinkedList对象：
>>> lst = LinkedList()
... for value in reversed((1, 1, 2, 2, 10, 12, 12, 13, 13, 25, 32, 39, 48, 65, 78)):
... lst.add(value)
...
>>> duplicates_sorted(lst)
Duplicates: [2, 12, 13]
>>> duplicates_sorted(lst.item)
Duplicates: [1, 2, 12, 13]
问题是Node和LinkedList都实现了get_next和item。然而，LinkedList.item返回Node，而Node.item返回原始值。
这意味着duplicates_sorted是为两者定义的，但仅对Node对象有意义。如果k是LinkedList，则以下内容将值与Node进行比较：
k.item == k.get_next().item
# ^ ^ 1
# Node(1, ...)
如果您希望duplicates_sorted成为一种方法，请先打开第一个元素：
class LinkedList:
...
def duplicates_sorted(self):
k = self.item # unpack first item
...
如果您希望两种类型都有效，则应确保duplicates_sorted根据输入类型展开：
def duplicates_sorted(num):
k = num.item if isinstance(num, LinkedList) else num
...
您的副本排序中有一个错误。错误会在第一个元素之后自行修复，因此如果前两个元素没有重复，则不会再现错误，但如果前2个元素是重复，则可以再现错误。
修复：
class LinkedList(object):
# ... snipp ...
# instance method of LinkedList
def duplicates_sorted(self):
k = self.item # this is the first item of self, NOT self itself.
# self itself would be a LinkedList()
duplicate_elements = []
while k is not None:
if k.get_next() is None:
break
if k.item == k.get_next().item:
duplicate_elements.append(k.item)
k = k.get_next()
print("Duplicates: ", duplicate_elements)
测试：
L = LinkedList()
for n in [1, 1, 2, 2, 10, 12, 12, 13, 13, 25, 32, 39, 48, 65, 78]:
L.add(n)
L.print_list()
L.duplicates_sorted()
L = LinkedList()
for n in [1, 1, 2, 2, 10, 12, 12, 13, 13, 25, 32, 39, 48, 65, 78] [::-1]:
L.add(n)
L.print_list()
L.duplicates_sorted()
输出：
Print List = 78, 65, 48, 39, 32, 25, 13, 13, 12, 12, 10, 2, 2, 1, 1
Duplicates: [13, 12, 2, 1]
Print List = 1, 1, 2, 2, 10, 12, 12, 13, 13, 25, 32, 39, 48, 65, 78
Duplicates: [1, 2, 12, 13]
作为非实例方法：
def duplicates_sorted(ll):
k = ll.item
duplicate_elements = []
while k is not None:
if k.get_next() is None:
break
if k.item == k.get_next().item:
duplicate_elements.append(k.item)
k = k.get_next()
print("Duplicates: ", duplicate_elements)