运用C语言编写简短的代码,将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据
时间: 2024-09-26 08:10:49 浏览: 30
在C语言中,可以使用迭代的方式合并两个递增有序链表,保持原链表节点的引用,并不创建新的节点。下面是一个简单的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 链表节点结构体
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 合并函数
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
// 初始化合并后的头结点
ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
dummy->next = NULL;
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; // 返回合并后的实际头部节点
}
// 测试
void printList(ListNode* head) {
ListNode* curr = head;
while (curr != NULL) {
printf("%d -> ", curr->val);
curr = curr->next;
}
printf("NULL\n");
}
int main() {
// 创建两个简单例子链表
ListNode* list1 = (ListNode*)malloc(sizeof(ListNode));
list1->val = 1;
list1->next = (ListNode*)malloc(sizeof(ListNode));
list1->next->val = 3;
list1->next->next = NULL;
ListNode* list2 = (ListNode*)malloc(sizeof(ListNode));
list2->val = 2;
list2->next = (ListNode*)malloc(sizeof(ListNode));
list2->next->val = 4;
list2->next->next = NULL;
// 合并并打印结果
ListNode* mergedList = mergeTwoLists(list1, list2);
printList(mergedList);
return 0;
}
```
在这个代码中,`mergeTwoLists` 函数接收两个递增有序链表的指针,通过循环比较和链接节点实现了合并。运行 `main` 函数可以看到合并后的链表。
阅读全文