写一个单链表冒泡排序

下面是单链表冒泡排序的示例代码（使用C++语言实现）：

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

// 冒泡排序函数
ListNode* bubbleSortList(ListNode* head) {
    // 如果链表为空或只有一个节点，直接返回
    if (!head || !head->next) {
        return head;
    }
    // 冒泡排序
    ListNode *cur = head, *tail = NULL;
    while (tail != head->next) {
        while (cur->next != tail) {
            if (cur->val > cur->next->val) {
                int temp = cur->val;
                cur->val = cur->next->val;
                cur->next->val = temp;
            }
            cur = cur->next;
        }
        tail = cur;
        cur = head;
    }
    return head;
}

这个函数的时间复杂度为 $O(n^2)$，其中 $n$ 是链表中节点的个数。可以看到，冒泡排序算法比较简单，但时间复杂度较高，对于大规模的数据不适合使用。