对带有头结点的单链表进行排序 用c＋＋语言

对带有头结点的单链表进行排序通常可以使用排序算法如插入排序、归并排序或快速排序等。这里我们以插入排序为例，因为插入排序适合处理已经部分有序的数据，对于链表操作相对简单。

**插入排序链表(C++)示例**:

#include <iostream>
using namespace std;

// 链表节点结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 插入排序链表函数
ListNode* insertionSortList(ListNode* head) {
    if (!head || !head->next) return head; // 如果链表为空或只有一个元素，直接返回

    ListNode* dummy = new ListNode(0); // 创建虚拟头节点
    dummy->next = head;

    ListNode* curr = head;
    ListNode* prev = dummy;
    
    while (curr != NULL && curr->next != NULL) {
        ListNode* temp = curr->next;
        
        if (curr->val > temp->val) { // 比较当前节点值与下一个节点值
            prev->next = temp; // 移动prev指向temp，以便后续交换
            while (temp != NULL && temp->val < curr->val) { // 跳过比curr小的节点
                prev = temp;
                temp = temp->next;
            }
            
            prev->next = curr; // 将curr移动到正确的位置
            curr->next = temp; // 当前节点指向下一个小于自己的节点
        } else {
            curr = curr->next;
        }
    }

    return dummy->next; // 返回新的链表头
}

// 打印链表
void printList(ListNode* head) {
    ListNode* node = head;
    while (node) {
        cout << node->val << " ";
        node = node->next;
    }
    cout << endl;
}

int main() {
    // 实例化一个链表并进行排序
    ListNode* list = new ListNode(4);
    list->next = new ListNode(2);
    list->next->next = new ListNode(1);
    list->next->next->next = new ListNode(3);

    cout << "Original List: ";
    printList(list);

    ListNode* sortedList = insertionSortList(list);
    cout << "Sorted List: ";
    printList(sortedList);

    return 0;
}

在这个例子中，`insertionSortList`函数通过不断比较节点值将链表按升序排列。排序后的链表仍然保持链表的形式。