有序链表的合并c语言
时间: 2024-04-12 12:21:39 浏览: 22
有序链表的合并是指将两个非降序链表S1和S2合并成一个新的非降序链表S3。可以使用循环来实现合并过程。具体步骤如下:
1. 创建一个新的链表S3。
2. 初始化三个指针:p1指向S1的头节点,p2指向S2的头节点,p3指向S3的头节点。
3. 比较p1和p2指向的节点的值,将较小的节点添加到S3中,并移动相应的指针。
4. 如果p1或p2指针为空,则将剩余的节点直接添加到S3的末尾。
5. 重复步骤3-4,直到p1和p2都为空。
6. 返回S3。
以下是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 = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->next = NULL;
struct ListNode* p3 = dummy;
// 循环比较l1和l2的节点值,将较小的节点添加到合并结果中
while (l1 && l2) {
if (l1->val <= l2->val) {
p3->next = l1;
l1 = l1->next;
} else {
p3->next = l2;
l2 = l2->next;
}
p3 = p3->next;
}
// 将剩余的节点添加到合并结果的末尾
if (l1) {
p3->next = l1;
}
if (l2) {
p3->next = l2;
}
return dummy->next;
}
int main() {
// 创建两个有序链表S1和S2
struct ListNode* S1 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* S2 = (struct ListNode*)malloc(sizeof(struct ListNode));
// 初始化S1和S2的节点值和指针
// ...
// 合并S1和S2得到S3
struct ListNode* S3 = mergeTwoLists(S1, S2);
// 打印合并后的链表S3的节点值
struct ListNode* p = S3;
while (p) {
printf("%d ", p->val);
p = p->next;
}
return 0;
}
```
相关推荐
![](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)
![](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)