试写一算法,实现单链表上的冒泡排序。
时间: 2023-03-20 07:06:49 浏览: 102
算法步骤:
1. 定义一个指针p,指向链表的头结点。
2. 定义两个指针p1和p2,分别指向链表的第一个节点和第二个节点。
3. 从链表的头结点开始,依次比较相邻的两个节点的值,如果前一个节点的值大于后一个节点的值,则交换它们的值。
4. 继续比较下一对相邻的节点,直到链表的末尾。
5. 如果在一次遍历中没有进行任何交换,则说明链表已经有序,排序结束。
6. 如果进行了交换,则继续进行下一次遍历,直到链表有序为止。
7. 最后返回排好序的链表。
代码实现:
```
void bubbleSort(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return;
}
ListNode* p = head;
bool flag = true;
while (flag) {
flag = false;
ListNode* p1 = head->next;
ListNode* p2 = p1->next;
while (p2 != nullptr) {
if (p1->val > p2->val) {
int temp = p1->val;
p1->val = p2->val;
p2->val = temp;
flag = true;
}
p1 = p1->next;
p2 = p2->next;
}
}
}
```