c语言中给链表节点排序
时间: 2023-08-15 07:32:14 浏览: 161
链表节点的排序可以使用各种排序算法,比如冒泡排序,插入排序,选择排序,快速排序等等。这里介绍一种插入排序的实现方法。
假设链表节点的结构体定义如下:
```c
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
```
下面是链表节点排序的代码实现:
```c
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head; // 如果链表为空或只有一个节点,则直接返回
ListNode *dummy = (ListNode*)malloc(sizeof(ListNode)); // 创建虚拟头节点
dummy->next = head;
ListNode *p = head->next, *q = head;
while (p) {
ListNode *prev = dummy;
while (prev->next->val < p->val && prev->next != p) {
prev = prev->next;
}
if (prev->next != p) {
q->next = p->next;
p->next = prev->next;
prev->next = p;
p = q->next;
} else {
q = p;
p = p->next;
}
}
head = dummy->next;
free(dummy);
return head;
}
```
该函数的时间复杂度为 O(n^2),空间复杂度为 O(1)。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)