运用C语言编写简单代码,将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据
时间: 2024-09-26 11:10:48 浏览: 30
在C语言中,合并两个递增有序链表可以采用迭代或递归的方式来实现。这里我们提供一个简单的迭代方法,假设`ListNode`结构包含`value`节点值和`next`指向下一个节点的指针。
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int value;
struct ListNode* next;
} ListNode;
// 合并两个递增有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) return l2; // 如果l1为空,返回l2
if (l2 == NULL) return l1; // 如果l2为空,返回l1
// 创建一个新的头结点,并初始化为当前链表的最小值
ListNode* head = l1->value < l2->value ? l1 : l2;
l1 = l1->value < l2->value ? l1->next : l1;
l2 = l2->value < l1->value ? l2->next : l2;
// 当其中一个链表遍历完时,将另一个剩余的链表添加到结果链表的末尾
while (l1 != NULL && l2 != NULL) {
if (l1->value <= l2->value) {
head->next = l1;
l1 = l1->next;
} else {
head->next = l2;
l2 = l2->next;
}
head = head->next;
}
// 将最后一个链表剩余的部分添加到结果链表的末尾
if (l1 != NULL) head->next = l1;
if (l2 != NULL) head->next = l2;
return head;
}
int main() {
// 测试示例
ListNode* list1 = malloc(sizeof(ListNode));
list1->value = 1;
list1->next = malloc(sizeof(ListNode));
list1->next->value = 3;
list1->next->next = NULL;
ListNode* list2 = malloc(sizeof(ListNode));
list2->value = 2;
list2->next = malloc(sizeof(ListNode));
list2->next->value = 4;
list2->next->next = NULL;
ListNode* mergedList = mergeTwoLists(list1, list2);
// 打印结果链表
while (mergedList != NULL) {
printf("%d -> ", mergedList->value);
mergedList = mergedList->next;
}
printf("NULL\n");
free(mergedList);
return 0;
}
```
阅读全文