c语言合并两个有序链表的方法是什么
合并两个有序链表的方法是使用双指针来比较两个链表的节点值,然后按照顺序将节点连接起来。
具体步骤如下:
- 定义一个新的链表头节点指针newHead,并且定义一个指针指向它,用于后续的节点的连接。
- 定义两个指针指向两个有序链表的头节点,分别命名为p1和p2,初始化为链表1和链表2的头节点。
- 遍历链表1和链表2,比较p1和p2指向节点的值: a. 若p1的值小于等于p2的值,则将p1指向的节点连接到newHead后面,并且将p1指针后移一位。 b. 若p1的值大于p2的值,则将p2指向的节点连接到newHead后面,并且将p2指针后移一位。
- 当其中一个链表遍历完毕后,将另一个链表剩余部分直接连接到newHead后面。
- 返回newHead的下一个节点,即为合并后的有序链表的头节点。
代码示例:
#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));
struct ListNode* p = newHead;
struct ListNode* p1 = l1;
struct ListNode* p2 = l2;
while (p1 && p2) {
if (p1->val <= p2->val) {
p->next = p1;
p1 = p1->next;
} else {
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
if (p1) {
p->next = p1;
}
if (p2) {
p->next = p2;
}
return newHead->next;
}
int main() {
// 创建链表1: 1 -> 2 -> 4
struct ListNode* l1 = (struct ListNode*)malloc(sizeof(struct ListNode));
l1->val = 1;
l1->next = (struct ListNode*)malloc(sizeof(struct ListNode));
l1->next->val = 2;
l1->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
l1->next->next->val = 4;
l1->next->next->next = NULL;
// 创建链表2: 1 -> 3 -> 4
struct ListNode* l2 = (struct ListNode*)malloc(sizeof(struct ListNode));
l2->val = 1;
l2->next = (struct ListNode*)malloc(sizeof(struct ListNode));
l2->next->val = 3;
l2->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
l2->next->next->val = 4;
l2->next->next->next = NULL;
// 合并两个有序链表
struct ListNode* mergedList = mergeTwoLists(l1, l2);
// 输出合并后的链表:1 -> 1 -> 2 -> 3 -> 4 -> 4
while (mergedList) {
printf("%d ", mergedList->val);
mergedList = mergedList->next;
}
return 0;
}
输出结果: 1 1 2 3 4 4