C语言:请设计一个算法并编程实现:将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。
时间: 2024-10-23 20:11:19 浏览: 48
在C语言中,我们可以使用迭代的方式来合并两个递增有序的链表,同时保持它们的递增顺序。下面是一个简单的算法设计:
首先,我们需要定义链表节点结构:
```c
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
```
然后,我们创建一个函数`mergeTwoLists`来合并两个链表:
```c
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 定义头结点作为临时指针
ListNode* dummy = (ListNode*)malloc(sizeof(ListNode)); // 使用堆内存防止空指针
dummy->val = INT_MIN; // 初始化值为所有输入值的下界
dummy->next = NULL;
// 迭代合并两个链表
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
dummy->next = l1;
l1 = l1->next;
} else {
dummy->next = l2;
l2 = l2->next;
}
dummy = dummy->next;
}
// 将剩余的一个链表连接到结果上
if (l1 != NULL) {
dummy->next = l1;
} else {
dummy->next = l2;
}
return dummy->next; // 返回新的头结点
}
```
这个函数通过比较当前节点的值,将较小的节点添加到新链表中,直到其中一个链表为空。最后,返回合并后的链表的头结点。
阅读全文