如何基于链表的顺序访问特性高效实现升序或降序排序？

你尝试的是类似冒泡排序的思路，时间复杂度为O(n²)，对于长链表来说效率确实极低。针对链表只能顺序访问的特性，归并排序是最适合的高效排序算法，时间复杂度稳定在O(n log n)，而且不需要像数组归并那样额外开辟大量空间，仅通过调整节点指针就能完成排序。

归并排序的链表实现思路 #

归并排序基于分治思想，核心步骤如下：

1. 拆分链表：用快慢指针法找到链表中间节点，将链表拆分为左右两个子链表。快慢指针的逻辑是：快指针每次走两步，慢指针每次走一步，当快指针到达链表末尾时，慢指针指向的就是中间节点。
2. 递归排序：分别对左右两个子链表递归执行归并排序。
3. 合并链表：将两个已排序的子链表合并为一个有序链表，合并时只需逐个比较两个子链表的节点，调整指针指向即可，无需移动节点数据。

C语言代码示例 #

#include <stdio.h>
#include <stdlib.h>

// 链表节点定义
typedef struct Item {
    int val;
    struct Item* next;
} Item;

// 判断链表是否为空
int listisempty(Item* head) {
    return head == NULL;
}

// 快慢指针法找链表中间节点
Item* findMiddle(Item* head) {
    if (listisempty(head) || listisempty(head->next)) {
        return head;
    }
    Item* slow = head;
    Item* fast = head->next;
    while (!listisempty(fast) && !listisempty(fast->next)) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// 合并两个有序链表
Item* merge(Item* left, Item* right) {
    Item dummy;
    Item* current = &dummy;
    dummy.next = NULL;
    
    while (!listisempty(left) && !listisempty(right)) {
        if (left->val <= right->val) {
            current->next = left;
            left = left->next;
        } else {
            current->next = right;
            right = right->next;
        }
        current = current->next;
    }
    // 拼接剩余未处理的节点
    current->next = listisempty(left) ? right : left;
    return dummy.next;
}

// 链表归并排序主函数
Item* mergeSort(Item* head) {
    if (listisempty(head) || listisempty(head->next)) {
        return head;
    }
    // 拆分链表
    Item* mid = findMiddle(head);
    Item* right = mid->next;
    mid->next = NULL; // 断开左右子链表
    
    // 递归排序子链表
    Item* sortedLeft = mergeSort(head);
    Item* sortedRight = mergeSort(right);
    
    // 合并有序子链表
    return merge(sortedLeft, sortedRight);
}

// 辅助函数：打印链表
void printList(Item* head) {
    Item* tmp = head;
    while (!listisempty(tmp)) {
        printf("%d ", tmp->val);
        tmp = tmp->next;
    }
    printf("\n");
}

// 测试用例
int main() {
    // 构建示例链表：3 -> 1 -> 4 -> 2
    Item* head = (Item*)malloc(sizeof(Item));
    head->val = 3;
    head->next = (Item*)malloc(sizeof(Item));
    head->next->val = 1;
    head->next->next = (Item*)malloc(sizeof(Item));
    head->next->next->val = 4;
    head->next->next->next = (Item*)malloc(sizeof(Item));
    head->next->next->next->val = 2;
    head->next->next->next->next = NULL;
    
    printf("排序前：");
    printList(head);
    
    head = mergeSort(head);
    
    printf("排序后：");
    printList(head);
    
    // 内存释放逻辑省略
    return 0;
}

其他可选方案：链表快速排序 #

虽然归并排序是链表排序的首选，但也可以实现链表版快速排序，平均时间复杂度为O(n log n)，不过最坏情况下仍为O(n²)，稳定性不如归并排序。其核心思路是：选取一个基准节点，将链表拆分为小于基准、等于基准、大于基准的三个部分，递归排序前后两部分后再拼接。但实现复杂度略高于归并排序，适合对平均性能有要求且能接受最坏情况风险的场景。

以上所有方案都无需直接访问链表尾节点，完全适配链表只能顺序访问的特性。

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