C语言 适用于链表的排序
时间: 2023-06-28 11:03:53 浏览: 51
是的,C语言可以很方便地实现链表的排序。常见的链表排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序等。
以插入排序为例,代码实现如下:
```c
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* insertionSortList(struct ListNode* head){
if (head == NULL || head->next == NULL) return head;
struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
dummy->next = head;
struct ListNode *cur = head->next, *pre = head;
while (cur) {
if (pre->val > cur->val) {
struct ListNode *p = dummy;
while (p->next->val < cur->val) p = p->next;
pre->next = cur->next;
cur->next = p->next;
p->next = cur;
cur = pre->next;
} else {
pre = cur;
cur = cur->next;
}
}
return dummy->next;
}
```
这里使用了插入排序的思想,将原链表分为已排序和未排序两部分,每次从未排序部分中取一个节点,插入到已排序部分中的合适位置。需要注意的是,为了方便操作,这里使用了一个虚拟头节点(dummy)。