在插入链表时管理重复项

Question

我编写了一种算法，用于插入按其number成员变量排序的Course对象链表中。它运行良好，除非我尝试插入重复项，例如 2420 的两个实例。列表__str__输出当前如下所示：

cs1400 Introduction to Programming Grade:3.6 Credit Hours: 4 
cs1410 C++ Programming Grade:2.6 Credit Hours: 4 
cs2420 Introduction to Data Structures Grade:3.2 Credit Hours: 4 
cs2810 Computer Architecture Grade:3.8 Credit Hours: 3 

这是我的插入方法代码

def insert(self, course=None):
"""Insert the specified Course in Course Number ascending order.""" 
def insert_helper(cursor, course):
if course is None:
return
if course.number <= self.head.number: # start of the list
self.head = course
return
if cursor.next is None or course.number <= cursor.next.number: # 
course.next = cursor.next
cursor.next = course
return
insert_helper(cursor.next, course)

if self.head is None:
self.head = course
return
cursor = self.head
insert_helper(cursor, course)

诀窍是将我的思想包裹在递归框架上。我希望尽快更好地掌握这一点。

Answer 1

我不认为重复的课程编号本身是问题所在。

您的程序中有一个错误：

if course.number <= self.head.number: # start of the list
self.head = course
return

如果您执行此代码片段中的最后两行，您的列表将变成一个包含course的单例列表，而不包含其他内容。

将此语句与下一个if语句进行比较，其中如果条件为 true，则执行

course.next = cursor.next

您需要在两个地方都course.next设置某些内容。

另请注意，如果在第一次调用insert_helper期间course.number <= self.head.number不为 true，则在任何递归调用中也不为 true。最好在第一次调用该函数之前处理这种情况。