单链表升序排序递归问题：首元素在二次递归中被忽略

问题描述 #

开发单链表升序排序程序时，遇到首元素在第二次递归调用中未正确归位的问题：输入链表7->1->8->0->NULL，输出为1->0->7->8->NULL，元素1没有被排序到应有的位置。

节点结构体 #

struct nodo {
    int elem;
    struct nodo *next;
};

问题代码 #

struct nodo *ordinaLista(struct nodo *head) {
    //in ordine crescente

    if (!head)
        return NULL;
    else {
        if ((head->next) && (head->elem >= head->next->elem)) {
            int tmp = head->elem;
            head->elem = head->next->elem;
            head->next->elem = tmp;
        }
        //printList(head);
        
        head->next = ordinaLista(head->next); 
        head->next = ordinaLista(head->next);
    }
    return head;
}

问题原因 #

1. 重复递归覆盖结果：代码中连续执行两次head->next = ordinaLista(head->next)，第一次递归已经完成后续链表的排序，但第二次递归会重新处理已排好的链表，直接覆盖之前的排序结果，导致前面的元素无法正确归位。
2. 逻辑不符合排序算法规则：当前逻辑仅做了相邻节点的单次交换，既没有实现冒泡排序“将最大元素逐步沉到链表末尾”的核心逻辑，也没有分治排序的分拆/合并步骤，本质上是错误的递归逻辑。

拿输入示例7->1->8->0走一遍关键流程：

• 首次进入函数，交换7和1，链表变为1->7->8->0。
• 第一次递归处理7->8->0，最终得到7->0->8，此时head->next被赋值为该结果，链表变为1->7->0->8。
• 第二次递归再次处理7->0->8，交换7和0得到0->7->8，head->next被覆盖为该结果，最终链表变为1->0->7->8，这就是元素1未正确排序的直接原因。

修正方案 #

下面是递归版冒泡排序的正确实现，核心逻辑是先将当前链表的最大元素沉到末尾，再递归处理前面的子链表：

struct nodo *ordinaLista(struct nodo *head) {
    // 递归终止条件：空链表或只有一个节点
    if (!head || !head->next)
        return head;

    // 遍历链表，将最大元素交换到末尾
    struct nodo *curr = head;
    while (curr->next != NULL) {
        if (curr->elem > curr->next->elem) {
            // 交换相邻节点的元素值
            int tmp = curr->elem;
            curr->elem = curr->next->elem;
            curr->next->elem = tmp;
        }
        curr = curr->next;
    }

    // 递归处理除最后一个节点外的子链表
    head->next = ordinaLista(head->next);

    return head;
}

该实现针对输入7->1->8->0会得到正确的升序结果0->1->7->8->NULL。

内容的提问来源于stack exchange，提问作者Luigi V.