请用C语言实现将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。
时间: 2024-06-15 07:08:10 浏览: 15
要实现将两个递增的有序链表合并为一个递增的有序链表,可以按照以下步骤进行:
1. 定义一个指针p指向第一个链表的头节点,定义一个指针q指向第二个链表的头节点。
2. 比较p和q指向的节点的值,将较小的节点插入到结果链表中,并将对应的指针后移一位。
3. 重复步骤2,直到其中一个链表遍历完毕。
4. 将未遍历完的链表剩余部分直接连接到结果链表的末尾。
下面是C语言实现的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 创建新节点
ListNode* createNode(int val) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
ListNode* p = l1;
ListNode* q = l2;
ListNode* dummy = createNode(0); // 创建一个虚拟头节点
ListNode* curr = dummy;
while (p != NULL && q != NULL) {
if (p->val <= q->val) {
curr->next = p;
p = p->next;
} else {
curr->next = q;
q = q->next;
}
curr = curr->next;
}
// 将未遍历完的链表剩余部分连接到结果链表的末尾
if (p != NULL) {
curr->next = p;
}
if (q != NULL) {
curr->next = q;
}
ListNode* result = dummy->next;
free(dummy);
return result;
}
// 打印链表
void printList(ListNode* head) {
ListNode* p = head;
while (p != NULL) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");
}
int main() {
// 创建两个有序链表
ListNode* l1 = createNode(1);
l1->next = createNode(3);
l1->next->next = createNode(5);
ListNode* l2 = createNode(2);
l2->next = createNode(4);
l2->next->next = createNode(6);
// 合并两个有序链表
ListNode* mergedList = mergeTwoLists(l1, l2);
// 打印合并后的链表
printList(mergedList);
// 释放内存
ListNode* p = mergedList;
while (p != NULL) {
ListNode* temp = p;
p = p->next;
free(temp);
}
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)