单链表冒泡法排序c++语言程序

单链表冒泡排序是一种简单的排序算法，它的工作原理类似于传统的数组冒泡排序，通过反复交换相邻节点如果它们当前的位置不符合升序或降序条件。但是因为链表的特点，我们需要借助额外的指针来辅助操作。

以下是C++中使用单链表实现冒泡排序的一个简化版本：

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

void bubbleSortList(ListNode*& head) {
    if (!head || !head->next) return; // 如果链表为空或只有一个元素，无需排序

    ListNode* end = nullptr, *temp = head;
    bool swapped;
    do {
        swapped = false;
        for (ListNode* curr = head; curr->next != end; curr = curr->next) {
            if (curr->val > curr->next->val) { // 比较并交换相邻节点
                std::swap(curr->val, curr->next->val);
                swapped = true;
            }
        }
        if (!swapped) break; // 如果一次遍历都没有发生交换，说明已经有序
        end = curr; // 更新end位置
    } while (true);
}

// 测试函数
void printList(ListNode* head) {
    ListNode* temp = head;
    while (temp) {
        std::cout << temp->val << " ";
        temp = temp->next;
    }
    std::cout << "\n";
}

int main() {
    ListNode* list = new ListNode{5};
    list->next = new ListNode{3};
    list->next->next = new ListNode{8};
    list->next->next->next = new ListNode{6};
    list->next->next->next->next = new ListNode{4};

    std::cout << "Before sorting:\n";
    printList(list);

    bubbleSortList(list);

    std::cout << "After sorting:\n";
    printList(list);

    return 0;
}

在这个程序中，`bubbleSortList`函数接受链表头结点作为参数，并在原地对链表进行排序。`printList`用于打印链表内容方便查看。注意，这个版本只实现了升序排序，如果你想实现降序，只需改变比较条件即可。