用c语言就地归并两个有序表
时间: 2024-09-27 07:03:52 浏览: 47
C语言数据结构 链表与归并排序实例详解
在C语言中,我们可以使用“就地归并”算法(In-place Merge)合并两个已经排序的链表。这种方法不需要额外的空间,而是通过修改原链表节点的指针来完成合并。这里是一个简单的示例:
```c
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 定义临时头节点和尾节点
ListNode dummy(0);
ListNode* tail = &dummy;
// 比较两个链表的节点值,将较小的节点添加到结果链表
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next; // 更新尾节点指向下一个位置
}
// 将剩余链表连接到已合并部分
if (l1 != NULL) {
tail->next = l1;
} else {
tail->next = l2;
}
return dummy.next; // 返回合并后的实际头部
}
```
这个函数会返回一个新的链表,其中包含了`l1`和`l2`的元素,按照升序排列。如果其中一个链表为空,则另一个链表的所有元素会被保留。
阅读全文