如何实现插入链表排序——按年龄排序

Question

这里怎么实现排序插入，我试了一段时间都没成功。

'isEmpty'方法检查head是否==NULL，insert at first方法在插入用户输入的详细信息后将指针指向NULL。

void insert(Person *&head, Person *&last, int age, string name, string surname, char gender)
{

    if(isEmpty(head))
        {
            insertAsFirst(head, last, age, name, surname, gender);
        }else
        {

        Person *temp = new Person;

         temp ->age = age;

         temp -> surname = surname;
         temp -> name = name;
         temp -> gender = gender;

         temp->next = NULL;
         last -> next = temp;
         last = temp;
            }
}

Answer 1

首先要避免创建未排序的列表：确保任何新节点立即插入右侧位置，保持列表排序。

假设您的所有其他代码都没有问题，您可以按如下方式进行。替换这些行：

 temp->next = NULL;
 last -> next = temp;
 last = temp;

...有了这个：

if (age <= head->age) {
    temp->next = head;
    head = temp;
    return;
}
Person *curr = head;
// Find insertion point
while (curr->next != nullptr && age > curr->next->age) {
    curr = curr->next;
}
// Insert new node after curr
temp->next = curr->next;
curr->next = temp;
if (temp->next == NULL) {
    last = temp;
}

如何实现插入链表排序——按年龄排序

How to implement insertion linked list sort - sort by age

c++

linked-list