链表插入重复元素故障：Course对象按number排序的插入算法问题

Let’s break this down step by step—first fixing the duplicate insertion bug, then unpacking how the recursion stack works here.

The Root Cause of the Duplicate (and Middle Insertion) Issue #

Looking at your insert_helper function, there’s a critical line you commented out that’s breaking all middle-position insertions (not just duplicates):

# course.next = cursor.next

When inserting a course between cursor and cursor.next, you need to first link the new course to the existing next node. Without this line, you’re overwriting cursor.next with the new course, which discards the rest of the list starting at cursor.next. This is especially obvious with duplicates because inserting a duplicate means placing it before an existing node with the same number—and that existing node gets lost entirely.

Corrected Insert Method #

Here’s the fixed code, with that line restored plus a small adjustment to handle the start-of-list insertion correctly:

def insert(self, course=None):
    """Insert the specified Course in Course Number ascending order."""
    def insert_helper(cursor, course):
        if course is None:
            return
        # Insert at the start if course number is <= head's number
        if course.number <= self.head.number:
            course.next = self.head  # Link new course to the old head
            self.head = course
            return
        # Found the insertion point: between cursor and cursor.next
        if cursor.next is None or course.number <= cursor.next.number:
            course.next = cursor.next  # Link new course to the next node
            cursor.next = course
            return
        # Move to the next node and recurse
        insert_helper(cursor.next, course)
    
    if self.head is None:
        self.head = course
        return
    cursor = self.head
    insert_helper(cursor, course)

We also added course.next = self.head for start-of-list inserts—this was missing too, which would have broken the list if you tried to replace an existing head with a new course.

How the Recursion Stack Works #

Let’s walk through an example to make this concrete. Suppose your current list is:
cs1400 -> cs1410 -> cs2420 -> cs2810
And you’re inserting a new cs2420 course.

1. First call: insert_helper(cursor=cs1400, course=new_cs2420)

   • new_cs2420.number (2420) is greater than self.head.number (1400), so we skip the start-of-list check.
   • cursor.next is cs1410, and 2420 > 1410, so we call insert_helper(cursor=cs1410, course=new_cs2420). This pushes the first call onto the recursion stack (like a bookmark for where we left off).

2. Second call: insert_helper(cursor=cs1410, course=new_cs2420)

   • 2420 > 1400 (head’s number), so we skip the start check again.
   • cursor.next is cs2420, and 2420 <= 2420 is true. We:
     • Set new_cs2420.next = cursor.next (links the new course to the existing cs2420).
     • Set cursor.next = new_cs2420 (links the previous node to our new course).
     • Return from this call, popping it off the recursion stack.

3. Back to the first call: Since the recursive call returned, we exit the first call too, and the insertion is complete.

The recursion stack acts like a series of bookmarks—each time we don’t find the insertion point, we save our current position and move to the next node. When we do find the right spot, we perform the insertion, then pop each bookmark off the stack as we return up the chain.

Testing the Fixed Code #

After fixing, inserting a duplicate cs2420 will result in the list:
cs1400 -> cs1410 -> new_cs2420 -> cs2420 -> cs2810
Which maintains ascending order and preserves all nodes in the list.

内容的提问来源于stack exchange，提问作者nrsmac