如何优化实现链表排序的Ordering函数 解决元素交换异常问题

原代码核心问题 #

• 交换逻辑无效：你当前写的Moving = Temp; Temp = Swapping;只是修改了函数内的局部临时指针变量，既没有改动链表节点的NextDiary指向，也没有修改节点存储的实际数据，链表的实际结构完全没有变化，自然看不到交换效果。
• 类型不匹配隐患：函数声明返回Naplo*类型，但空链表分支直接写return;无返回值，且最终返回的List是Diary*类型，类型不一致，推测应该是Naplo和Diary是同类型的别名，注意统一即可。
• 排序条件易混淆：原判断逻辑是Temp时间小于Moving时间就交换，最终得到的是按时间降序排列的链表，如果需要升序需要把小于号改成大于号。

优化实现方案 #

方案1：交换节点数据（实现最简单，适合节点数据量小的场景） #

不需要修改链表的指针连接，直接交换两个节点的存储数据即可，改动最小：

// 如果Naplo是Diary的别名，也可以写为Naplo* Ordering(Naplo* List)
Diary* Ordering(Diary* List)
{
    Diary* Temp;
    Diary* Moving;
    if (List == NULL)
        return NULL;
    
    for(Temp = List; Temp != NULL; Temp = Temp->NextDiary)
    {
        for (Moving = Temp->NextDiary; Moving != NULL; Moving = Moving->NextDiary)
        {
            // 以下为升序判断，要降序的话把>换回<即可
            if (Temp->Time.h > Moving->Time.h 
                || (Temp->Time.h == Moving->Time.h
                 && Temp->Time.m > Moving->Time.m))
            {
                // 交换两个节点的时间字段，有其他业务字段也同理补充交换
                Time tempTime = Temp->Time;
                Temp->Time = Moving->Time;
                Moving->Time = tempTime;
                // 比如还有内容字段的话补充：
                // char tempContent[256];
                // strcpy(tempContent, Temp->content);
                // strcpy(Temp->content, Moving->content);
                // strcpy(Moving->content, tempContent);
            }
        }
    }
    return List;
}

方案2：交换节点位置（适合节点数据量大的场景） #

如果节点存储的数据量很大，交换数据的成本太高，可以直接修改节点的前驱指针来交换节点位置，需要额外记录每个节点的前驱节点：

Diary* Ordering(Diary* List) {
    if (List == NULL || List->NextDiary == NULL)
        return List;
    
    // 虚拟头节点，方便处理头节点交换的情况
    Diary dummy;
    dummy.NextDiary = List;
    Diary* preTemp = &dummy;
    
    for (Diary* Temp = List; Temp != NULL; Temp = Temp->NextDiary) {
        Diary* minNode = Temp;
        Diary* preMin = preTemp;
        Diary* preMoving = Temp;
        for (Diary* Moving = Temp->NextDiary; Moving != NULL; Moving = Moving->NextDiary) {
            // 升序判断，要降序改>为<
            if (Moving->Time.h < minNode->Time.h 
                || (Moving->Time.h == minNode->Time.h && Moving->Time.m < minNode->Time.m)) {
                minNode = Moving;
                preMin = preMoving;
            }
            preMoving = Moving;
        }
        // 如果最小节点不是当前Temp节点，交换两个节点位置
        if (minNode != Temp) {
            preTemp->NextDiary = minNode;
            preMin->NextDiary = Temp;
            Diary* tempNext = Temp->NextDiary;
            Temp->NextDiary = minNode->NextDiary;
            minNode->NextDiary = tempNext;
            // 交换后Temp更新为minNode
            Temp = minNode;
        }
        preTemp = Temp;
    }
    return dummy.NextDiary;
}

内容的提问来源于stack exchange，提问作者Kövesdi László