首页定义一个函数，输入一个链表的头结点，将链表从小到大排序

定义一个函数，输入一个链表的头结点，将链表从小到大排序

时间: 2024-12-28 18:24:37 浏览: 23

实现单链表升序排序

对于单链表的升序排序，可以采用多种方法。这里介绍一种基于插入排序的思想来实现该功能。此方法通过构建一个新的有序链表来完成排序过程。

定义节点结构如下：

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

创建一个辅助函数用于将节点按照从小到大的顺序插入新的链表中:

Node* insertInOrder(Node*&amp; sortedHead, Node* newNode) {
    if (!sortedHead || (newNode->data <= sortedHead->data)) { 
        newNode->next = sortedHead; 
        return newNode; 
    }
    
    Node* current = sortedHead;
    while ((current->next != nullptr) &amp;&amp; (current->next->data < newNode->data))
        current = current->next;

    newNode->next = current->next;
    current->next = newNode;

    return sortedHead;
}

接下来是具体的sort_list函数实现，它接收原始未排序的链表作为输入并返回已排序的结果[^1]:

void sort_list(Node*&amp; headRef) {
    Node* result = nullptr; // 新建一个空列表用来存储已经排好序的数据
    
    while (headRef != nullptr) {
        Node* temp = headRef;       // 取出当前要处理的第一个元素
        headRef = headRef->next;     // 更新旧链表头部指向下一个位置
        
        result = insertInOrder(result, temp);  // 将取出的元素加入到新链表里
    }

    headRef = result;               // 把最终得到的新链表赋给原来的引用变量
}

上述代码实现了对单向链表进行升序排列的功能。每次从未排序部分取第一个结点出来，并将其正确地放置于正在形成的有序序列之中直到全部数据都被重新安排完毕为止[^3]。