为什么我的链表排序不正确？

Question

我试图将按日期排序的新约会插入到链接列表中，但当我去测试它时，总会有一个实例排序不正确。目前这是我的代码：

from datetime import datetime

class VaccList:
    class Appointment:
        def __init__(self, name, age, city, date):
            assert type(name) is str, 'name variable must be a string'
            assert type(age) is int, 'age variable must be a integer'
            assert type(city) is str, 'city variable must be a string'
            assert type(date) is datetime, 'date variable must be a datetime object'
            assert name != None, 'name variable cannot be empty'
            assert age >= 18 and age <= 100, 'age must be between 18 and 100'
            #   ADD 6 asserts.  4 for the types and name cannot be empty, 
            #   and age must be between 18 and 100

            self.name = name
            self.age = age
            self.city = city
            self.date = date
            self.confirmed = False
            self.next = None

        def __str__(self):
            s = "Appointment for " + self.name + " on " + str(self.date) + " age:" + str(self.age) + "  city:" + self.city
            if self.confirmed:
                s += " (confirmed)"
            else:
                s += " (unconfirmed)"
            return s

    def __init__(self):
        self.head = None
        self.tail = None
    
    def print(self):       #YOU WRITE THIS (EASY)
        '''
        Print all the appointments, one per line.  Print a blank line after the last one.
        If the list is empty, print a line saying the Appointment List is empty.
        '''
        runner = self.head
        while runner != None:
            print(runner)
            runner = runner.next
    

    def insertByDate(self, newAppt):          #### YOU WRITE (HARD)
        ''' Given a pointer to an Appointment object, put it into the list so that the list remains sorted by date.
           Obviously the linked list may be empty, which is easy.  But inserting the newAppt in sorted order
           may mean putting it at the front if the newAppt's date is less than the first.  Or at the end, or in
           the middle.
        '''
        assert type(newAppt) is VaccList.Appointment, 'insertByDate requires a pointer to an appointment object'
        newnode = newAppt

        if self.head is None:
            self.head = newAppt
        elif newAppt.date < self.head.date:
            newAppt.next = self.head
            self.head = newAppt
        else:
            current = self.head
            while current.next != None and current.date < newAppt.date:
                current = current.next
            newAppt.next = current.next
            current.next = newAppt

这是我正在尝试运行的测试代码：

active =VaccList()

appt = VaccList.Appointment("Henry", 72, "Buffalo", datetime(2021,5,1,12,0,0))
active.insertByDate(appt)
appt = VaccList.Appointment("John", date=datetime(2021,3,10,12,0,0), age=75, city="Buffalo")
active.insertByDate(appt)
appt = VaccList.Appointment(date = datetime(2021, 3, 5, 8, 0, 0), name="Mary", city="Buffalo", age=65)
active.insertByDate(appt)
appt = VaccList.Appointment(date = datetime(2021, 4, 28, 13, 30, 0), name="Alvin", city="New York City", age=39)
active.insertByDate(appt)
appt = VaccList.Appointment(date = datetime(2021, 4, 21, 14, 0, 0), name="Sheila", city="New York City", age=50)
active.insertByDate(appt)
appt = VaccList.Appointment(date = datetime(2021, 3, 12, 18, 0, 0), name="Melvin", city="New York City", age=80)
active.insertByDate(appt)

active.print()

然而，每次我运行此命令时，“Henry”下的约会都会被错误地排序。我迷路了，因为它似乎把其余的约会都安排得很好，除了“亨利”不合适。非常感谢您的任何想法/解决方案，因为这是我的第一个python项目之一

Appointment for Mary on 2021-03-05 08:00:00 age:65  city:Buffalo (unconfirmed)
Appointment for John on 2021-03-10 12:00:00 age:75  city:Buffalo (unconfirmed)
Appointment for Henry on 2021-05-01 12:00:00 age:72  city:Buffalo (unconfirmed)
Appointment for Melvin on 2021-03-12 18:00:00 age:80  city:New York City (unconfirmed)
Appointment for Sheila on 2021-04-21 14:00:00 age:50  city:New York City (unconfirmed)
Appointment for Alvin on 2021-04-28 13:30:00 age:39  city:New York City (unconfirmed)

Answer 1

在else块中，循环正在查找一个current节点，使其日期位于要插入的节点的日期之后。但要意识到这会让你走得太远。。。您将在current之后插入新节点，因此current必须仍然是一个日期在插入的节点之前的节点

因此，改变这一点：

 while current.next != None and current.date < newAppt.date:

致：

 while current.next != None and current.next.date < newAppt.date:
 #                                     ^^^^^