c语言合并两个单链表LA和LB,把两个递增的单链表La,Lb,合并成一个递减的单链表Lc
时间: 2024-02-13 11:07:27 浏览: 87
可以按照以下步骤来合并两个单链表:
1. 首先判断La和Lb是否为空链表,如果有一个为空,则直接返回另一个链表。
2. 创建一个新的链表Lc,用于存储合并后的递减链表。
3. 遍历La和Lb,比较两个链表当前节点值的大小,将较大的节点插入Lc的头部。
4. 如果La或Lb还有剩余节点,将剩余节点直接插入Lc的头部。
5. 返回Lc。
下面是C语言的实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
ListNode* mergeList(ListNode* La, ListNode* Lb)
{
if (La == NULL) return Lb;
if (Lb == NULL) return La;
ListNode* Lc = NULL;
ListNode* pa = La;
ListNode* pb = Lb;
while (pa && pb) {
if (pa->val > pb->val) {
ListNode* temp = pa;
pa = pa->next;
temp->next = Lc;
Lc = temp;
}
else {
ListNode* temp = pb;
pb = pb->next;
temp->next = Lc;
Lc = temp;
}
}
if (pa) {
pa->next = Lc;
Lc = pa;
}
if (pb) {
pb->next = Lc;
Lc = pb;
}
return Lc;
}
int main()
{
ListNode* La = (ListNode*)malloc(sizeof(ListNode));
La->val = 1;
La->next = (ListNode*)malloc(sizeof(ListNode));
La->next->val = 3;
La->next->next = (ListNode*)malloc(sizeof(ListNode));
La->next->next->val = 5;
La->next->next->next = NULL;
ListNode* Lb = (ListNode*)malloc(sizeof(ListNode));
Lb->val = 2;
Lb->next = (ListNode*)malloc(sizeof(ListNode));
Lb->next->val = 4;
Lb->next->next = (ListNode*)malloc(sizeof(ListNode));
Lb->next->next->val = 6;
Lb->next->next->next = NULL;
ListNode* Lc = mergeList(La, Lb);
while (Lc) {
printf("%d ", Lc->val);
Lc = Lc->next;
}
printf("\n");
return 0;
}
```
输出结果为:6 5 4 3 2 1,表示合并后的递减链表Lc为6->5->4->3->2->1。
阅读全文