单链表冒泡排序

单链表冒泡排序的基本思想和数组冒泡排序类似，都是通过交换相邻元素的位置来达到排序的目的。具体实现步骤如下：

1. 定义两个指针p和q，p指向链表头结点，q指向链表第二个结点。

2. 使用双重循环遍历链表，外层循环控制比较次数，内层循环控制比较并交换操作。

3. 如果p指向的结点的值大于q指向的结点的值，则交换它们的值。

4. 内层循环结束后，q指针指向链表尾部，将p指针后移一位，重复执行步骤2和步骤3，直到p指向链表的倒数第二个结点。

5. 最后得到的链表就是排好序的链表。

下面是具体的实现代码：

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

ListNode* bubbleSortList(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    ListNode *p, *q, *tail;
    tail = NULL;
    while (head != tail) {
        p = head;
        q = p->next;
        while (q != tail) {
            if (p->val > q->val) {
                swap(p->val, q->val);
            }
            p = p->next;
            q = q->next;
        }
        tail = p;
    }
    return head;
}