将两个递增的有序链表合并为一个递增的有序链表,要求结果链表仍使用原来两个链表的存储空间,表中不允许有重复的数据。请用C语言编写代码。
时间: 2023-07-17 19:12:48 浏览: 114
您好!以下是使用C语言编写的合并两个递增有序链表的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 链表节点的结构体定义
struct ListNode {
int val;
struct ListNode* next;
};
// 合并两个递增有序链表的函数
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
// 创建一个哨兵节点作为合并后链表的头节点
struct ListNode dummy;
dummy.next = NULL;
struct ListNode* tail = &dummy;
// 依次比较两个链表的节点,并将较小的节点插入到合并后链表的尾部
while (l1 && l2) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
tail->next = NULL;
}
// 将剩余的节点直接插入到合并后链表的尾部
if (l1) {
tail->next = l1;
}
if (l2) {
tail->next = l2;
}
// 返回合并后链表的头节点(除哨兵节点外的第一个节点)
return dummy.next;
}
// 创建链表节点的函数
struct ListNode* createNode(int val) {
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 打印链表的函数
void printList(struct ListNode* head) {
while (head) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
int main() {
// 创建两个递增有序链表
struct ListNode* l1 = createNode(1);
l1->next = createNode(3);
l1->next->next = createNode(5);
struct ListNode* l2 = createNode(2);
l2->next = createNode(4);
l2->next->next = createNode(6);
// 合并两个链表
struct ListNode* mergedList = mergeTwoLists(l1, l2);
// 打印合并后的链表
printList(mergedList);
// 释放链表节点的内存
struct ListNode* temp;
while (mergedList) {
temp = mergedList;
mergedList = mergedList->next;
free(temp);
}
return 0;
}
```
这段代码中,我们首先创建了两个递增有序链表 `l1` 和 `l2`,然后调用 `mergeTwoLists` 函数将两个链表合并为一个递增有序链表,并将合并后的链表打印输出。最后,我们释放了合并后链表节点的内存空间,避免内存泄漏。
希望这段代码能够帮助到您!如果还有其他问题,请随时提问。
阅读全文