如何实现链表插入排序：按年龄字段排序

你当前的insert函数为直接追加到链表末尾的尾插逻辑，以下是修改为插入排序（默认按年龄升序排列，可自行替换排序字段）的代码及说明：

核心逻辑改动 #

• 新增新节点插入位置的遍历查找逻辑，保证插入后链表始终有序
• 兼容空链表、插入到头部、插入到中间、插入到尾部4种场景
• 保留原有head、last指针的更新规则，不影响其他逻辑调用

修改后代码 #

void insert(Person *&head, Person *&last, int age, string name, string surname, char gender)
{
    // 先创建待插入的新节点
    Person *temp = new Person;
    temp->age = age;
    temp->surname = surname;
    temp->name = name;
    temp->gender = gender;
    temp->next = NULL;

    // 情况1：链表为空，直接作为第一个节点插入
    if(isEmpty(head))
    {
        insertAsFirst(head, last, age, name, surname, gender);
        // 若insertAsFirst内部会自行创建节点，需删除此处temp避免内存泄漏；如果可以直接复用temp节点可删除本行
        delete temp;
        return;
    }

    // 情况2：新节点排序字段比头节点更小，插入到链表头部
    if (temp->age < head->age)
    {
        temp->next = head;
        head = temp;
        return;
    }

    // 情况3：遍历链表找到合适的插入位置
    Person *current = head;
    // 找到第一个下一个节点字段大于新节点的前置位置，<=规则保证排序稳定性
    while (current->next != NULL && current->next->age <= temp->age)
    {
        current = current->next;
    }

    // 完成节点插入
    temp->next = current->next;
    current->next = temp;

    // 若新节点插入到尾部，更新last指针
    if (temp->next == NULL)
    {
        last = temp;
    }
}

注意事项 #

• 如需调整排序规则，比如按姓名、姓氏排序，只需要替换判断条件中的age为对应字段即可，字符串比较可直接用<=运算符
• 插入排序单步插入时间复杂度为O(n)，适合小规模数据的链表排序场景

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