两个有序链表的合并 c
时间: 2024-06-13 22:06:30 浏览: 19
以下是两种C语言合并两个有序链表的方法:
方法一:递归法
```c
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
int main() {
// 创建链表1
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
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* result = mergeTwoLists(l1, l2);
// 输出结果
while (result != NULL) {
printf("%d ", result->val);
result = result->next;
}
return 0;
}
```
方法二:迭代法
```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));
struct ListNode* cur = dummy;
while (l1 != NULL && l2 != NULL) {
if (l1->val <= l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 == NULL ? l2 : l1;
return dummy->next;
}
int main() {
// 创建链表1
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
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* result = mergeTwoLists(l1, l2);
// 输出结果
while (result != NULL) {
printf("%d ", result->val);
result = result->next;
}
return 0;
}
```