写一个链表的冒泡排序
时间: 2023-07-25 09:10:58 浏览: 53
链表的冒泡排序与数组的冒泡排序类似,只不过需要对节点进行交换而不是对元素进行交换。下面是一个用 C 语言实现的链表冒泡排序算法:
```c
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* bubble_sort(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode* p;
struct ListNode* q;
struct ListNode* tail = NULL;
do {
p = head;
while (p->next != tail) {
if (p->val > p->next->val) {
if (p == head) {
head = p->next;
}
q = p->next;
p->next = q->next;
q->next = p;
p = q;
}
p = p->next;
}
tail = p;
} while (head != tail);
return head;
}
```
其中,`struct ListNode` 是链表节点的结构体定义,`head` 是链表的头节点。算法的时间复杂度为 $O(n^2)$,空间复杂度为 $O(1)$。