C语言单链表排序时元素反复交换问题排查与修复

• 1. 新节点重复插入错误：当前的插入逻辑放在循环体里，每轮遍历只要prev->age < newPerson->age就会执行一次插入，会导致同一个新节点被反复插入链表，直接打乱原有链表结构。
• 2. 节点交换逻辑不完整：交换相邻节点时仅修改了两个节点自身的next指针，没有修改这两个节点的前驱节点的next指向，导致链表断链、出现环，这就是Sven和Bob反复交换的核心原因。比如原链表结构为前序节点 -> prev -> curr -> 后续节点，交换后前序节点的next还是指向原来的prev，整个链表结构直接错乱。
• 3. 遍历指针更新逻辑错误：交换prev和curr后，两个指针的相对位置已经发生变化，依然按原逻辑执行prev = prev->next; curr = curr->next会出现跳节点、重复遍历的问题，甚至陷入死循环。
• 4. 相等年龄直接退出逻辑错误：遇到年龄相等的节点就直接return，后续未处理的节点全部被忽略，排序逻辑提前中断。

这里调整实现逻辑：先将新节点插入到链表头部，再通过冒泡排序对整个链表做降序排列，规避插入和排序耦合导致的逻辑混乱，修复后代码如下：

// 冒泡排序实现链表降序排序，支持插入新节点后排序
void sortPerson(person *pers, person* newPerson)
{
    if(pers == NULL)
    {
        printf("List is empty");
        return;
    }
    // 先把新节点插到链表头部
    newPerson->next = pers->next;
    pers->next = newPerson;

    int swapped;
    person *ptr1;
    person *lptr = NULL;
    person *head = pers;

    do
    {
        swapped = 0;
        ptr1 = head;
        // 遍历未排序段
        while (ptr1->next != lptr)
        {
            if (ptr1->age < ptr1->next->age)
            { 
                // 交换两个节点的内容，不用修改指针，更简单不易出错
                // 交换姓名
                char* tempName = ptr1->name;
                ptr1->name = ptr1->next->name;
                ptr1->next->name = tempName;
                // 交换年龄
                int tempAge = ptr1->age;
                ptr1->age = ptr1->next->age;
                ptr1->next->age = tempAge;
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    } while (swapped);
}

修复说明 #

• 把插入新节点和排序逻辑拆分，先统一把新节点插到表头，再整体排序，避免重复插入问题
• 采用交换节点内容的方式实现排序，不需要修改前驱指针，大幅降低链表排序的出错概率
• 用冒泡排序的标准实现，避免出现跳节点、死循环的问题
• 删除了错误的提前return逻辑，保证所有节点都能被遍历排序

如果确实需要修改指针交换节点而非交换内容，可以参考标准链表节点交换实现，需要额外记录每对节点的前驱节点，修改前驱的next指向即可。

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