c语言合并两个有序链表,使之仍然有序。
时间: 2024-03-18 09:41:52 浏览: 14
合并两个有序链表可以使用归并排序的思想,具体步骤如下:
1. 新建一个头结点,用于指向合并后的链表。
2. 分别用指针 p1 和 p2 指向两个有序链表的头结点。
3. 新建一个指针 p3,用于指向合并后链表的尾结点。
4. 比较 p1 和 p2 结点的值,将较小的结点插入到 p3 的后面,并将 p1 或 p2 指针后移一位。
5. 重复步骤 4 直到两个链表中有一个为空。
6. 将另一个非空链表接到合并后链表的尾部。
下面是 C 语言实现的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = (ListNode*)malloc(sizeof(ListNode)); // 新建头结点
ListNode* p3 = dummy; // p3 指向合并后链表的尾结点
while (l1 && l2) { // 比较 l1 和 l2 结点的值,将较小的结点插入到 p3 的后面
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() {
// 新建两个有序链表
ListNode* l1 = (ListNode*)malloc(sizeof(ListNode));
l1->val = 1;
ListNode* l1_1 = (ListNode*)malloc(sizeof(ListNode));
l1_1->val = 2;
ListNode* l1_2 = (ListNode*)malloc(sizeof(ListNode));
l1_2->val = 4;
l1->next = l1_1;
l1_1->next = l1_2;
l1_2->next = NULL;
ListNode* l2 = (ListNode*)malloc(sizeof(ListNode));
l2->val = 1;
ListNode* l2_1 = (ListNode*)malloc(sizeof(ListNode));
l2_1->val = 3;
ListNode* l2_2 = (ListNode*)malloc(sizeof(ListNode));
l2_2->val = 4;
l2->next = l2_1;
l2_1->next = l2_2;
l2_2->next = NULL;
// 合并两个有序链表
ListNode* merged = mergeTwoLists(l1, l2);
// 输出合并后的链表
ListNode* p = merged;
while (p) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");
return 0;
}
```
输出结果为:1 1 2 3 4 4。