用c语言写:将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中不允许有重复的数据。
时间: 2024-10-10 16:12:41 浏览: 60
C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
在C语言中,合并两个递增的有序链表可以使用迭代或者递归的方式实现。这里提供一个迭代方法的例子:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 合并链表函数
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 创建新的头节点
ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
dummy->val = INT_MIN; // 设置初始值为链表最小可能值,避免插入重复元素
dummy->next = NULL;
// 定义三个指针:l1、l2 和合并后的链表当前节点
ListNode* curr = dummy;
while (l1 != NULL && l2 != NULL) {
if (l1->val <= l2->val) { // 如果l1较小,将其添加到新链表
curr->next = l1;
l1 = l1->next;
} else { // 否则,l2较小,添加到新链表
curr->next = l2;
l2 = l2->next;
}
curr = curr->next; // 移动curr指向下一个位置
}
// 将剩余未处理的链表连接到新链表尾部
if (l1 != NULL) {
curr->next = l1;
} else if (l2 != NULL) {
curr->next = l2;
}
return dummy->next; // 返回新链表的头节点,注意去掉dummy
}
// 测试
int main() {
// 创建两个示例链表...
ListNode* l1 = ...;
ListNode* l2 = ...;
// 合并链表
ListNode* result = mergeTwoLists(l1, l2);
// 打印合并后的链表
while (result != NULL) {
printf("%d -> ", result->val);
result = result->next;
}
printf("NULL\n");
// 释放内存
free(l1);
free(l2);
return 0;
}
```
阅读全文