用C语言实现将两个递增的有序链表合并为一个递增的有序链表。要求,结果链表仍使用原来两个链表的存储空间。不另外占用其他的存储空间。表中不允许有重复的数字
时间: 2024-06-15 07:08:11 浏览: 91
要实现将两个递增的有序链表合并为一个递增的有序链表,可以按照以下步骤进行:
1. 定义一个新的指针变量,用于指向合并后的链表的头节点。
2. 比较两个链表的头节点的值,将较小的节点作为合并后链表的头节点,并将指针指向该节点。
3. 分别定义两个指针变量,分别指向两个链表的当前节点。
4. 通过比较两个当前节点的值,将较小的节点连接到合并后链表的尾部,并更新指针。
5. 重复步骤4,直到其中一个链表遍历完毕。
6. 将另一个链表剩余的节点直接连接到合并后链表的尾部。
7. 返回合并后链表的头节点。
下面是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* mergedHead = NULL;
// 定义一个指针变量,用于指向合并后链表的当前节点
struct ListNode* mergedCurr = NULL;
// 判断两个链表是否为空
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
// 比较两个链表的头节点的值,将较小的节点作为合并后链表的头节点,并将指针指向该节点
if (l1->val <= l2->val) {
mergedHead = l1;
l1 = l1->next;
} else {
mergedHead = l2;
l2 = l2->next;
}
mergedCurr = mergedHead;
// 通过比较两个当前节点的值,将较小的节点连接到合并后链表的尾部,并更新指针
while (l1 != NULL && l2 != NULL) {
if (l1->val <= l2->val) {
mergedCurr->next = l1;
l1 = l1->next;
} else {
mergedCurr->next = l2;
l2 = l2->next;
}
mergedCurr = mergedCurr->next;
}
// 将另一个链表剩余的节点直接连接到合并后链表的尾部
if (l1 != NULL) {
mergedCurr->next = l1;
}
if (l2 != NULL) {
mergedCurr->next = l2;
}
return mergedHead;
}
// 创建链表节点
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) {
struct ListNode* curr = head;
while (curr != NULL) {
printf("%d ", curr->val);
curr = curr->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* curr = mergedList;
while (curr != NULL) {
struct ListNode* temp = curr;
curr = curr->next;
free(temp);
}
return 0;
}
```
阅读全文