C语言设计两个有序单列表的合并排序算法。
时间: 2024-09-17 15:09:43 浏览: 61
c语言合并两个已排序数组的示例(c语言数组排序)
5星 · 资源好评率100%
C语言中可以使用归并排序算法来合并两个已排序的单链表。归并排序是一种分治策略,将大的问题分解成小的子问题,然后递归地解决,最后合并结果。以下是合并两个有序链表的基本步骤:
1. 定义一个新的头节点,用于存储合并后的链表。
2. 比较两个链表当前节点的值。如果左侧链表的节点值较小,则将其添加到新链表,并移动指针到下一个节点;否则,从右侧链表添加。
3. 重复步骤2,直到其中一个链表遍历完。此时,如果还有剩余的节点未处理,将另一个链表剩余部分直接添加到新链表。
4. 最后,新链表的头节点就是合并后的有序链表。
这是一个伪代码示例:
```c
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
// 创建新的头节点
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->next = NULL;
// 分别指向l1、l2和新链表的头
struct ListNode* cur1 = l1;
struct ListNode* cur2 = l2;
struct ListNode* head = dummy;
while (cur1 && cur2) {
if (cur1->val <= cur2->val) {
head->next = cur1;
cur1 = cur1->next;
} else {
head->next = cur2;
cur2 = cur2->next;
}
head = head->next;
}
// 将剩余未处理的部分连接到新链表
if (cur1)
head->next = cur1;
else
head->next = cur2;
return dummy->next;
}
```
阅读全文