合并两个有序链表c语言
时间: 2023-09-08 07:15:39 浏览: 191
要在C语言中合并两个有序链表,可以按照以下步骤进行操作:
1. 定义一个新的链表头指针newHead,并用一个变量指向它。同时定义一个指针变量指向第一个链表的头节点,一个指针变量指向第二个链表的头节点。
2. 判断两个链表是否都遍历完,如果有一个链表已经遍历完了,则将另一个链表剩余的部分直接连接到新链表的尾部。
3. 如果两个链表都还有节点未遍历完,则比较两个链表当前节点的值,将较小的值节点连接到新链表的尾部,并将相应链表的指针向后移动一位。
4. 重复步骤3,直到有一个链表遍历完。
5. 最后,将新链表的头指针返回作为合并后的有序链表的头。
示例代码如下所示:
```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* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
newHead->next = NULL;
// 定义指针变量指向新链表的尾节点
struct ListNode* tail = newHead;
// 遍历两个链表,将较小值的节点连接到新链表的尾部
while (l1 && l2) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
// 将剩余的节点连接到新链表的尾部
if (l1) {
tail->next = l1;
}
if (l2) {
tail->next = l2;
}
// 返回新链表的头指针
return newHead->next;
}
int main() {
// 创建两个有序链表
struct ListNode* l1 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* l2 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* node1 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* node2 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* node3 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* node4 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* node5 = (struct ListNode*)malloc(sizeof(struct ListNode));
l1->val = 1;
l2->val = 1;
node1->val = 2;
node2->val = 3;
node3->val = 4;
node4->val = 4;
node5->val = 5;
l1->next = node1;
node1->next = node3;
node3->next = NULL;
l2->next = node2;
node2->next = node4;
node4->next = node5;
node5->next = NULL;
// 合并两个有序链表
struct ListNode* mergedList = mergeTwoLists(l1, l2);
// 输出合并后的链表结果
while (mergedList) {
printf("%d ", mergedList->val);
mergedList = mergedList->next;
}
return 0;
}
```
这段代码中,我们首先定义了一个新链表的头指针newHead,并用一个tail指针变量指向它,作为新链表的尾节点。然后通过遍历两个有序链表,将较小值的节点连接到新链表的尾部,直到其中一个链表遍历完。最后,将剩余的节点连接到新链表的尾部,并返回新链表的头指针作为合并后的有序链表的头。运行代码后,会输出合并后的链表结果。<span class="em">1</span><span class="em">2</span>
#### 引用[.reference_title]
- *1* *2* [C语言怎么合并两个有序链表](https://blog.csdn.net/LxXlc468hW35lZn5/article/details/119975521)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]