C语言写个算法,采用头插法将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中允许有重复的数据。
时间: 2023-05-13 10:06:52 浏览: 75
一算法可实现两个非递减的线性表的合并,采用链式存储结构,能够输出合并前和合并后链表的内容
以下是C语言实现头插法合并两个非递减的有序链表为一个非递增的有序链表的算法:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode *p1 = l1, *p2 = l2, *prev = NULL;
while (p1 && p2) {
if (p1->val <= p2->val) {
prev = p1;
p1 = p1->next;
} else {
ListNode *tmp = p2->next;
p2->next = p1;
if (prev) {
prev->next = p2;
} else {
l1 = p2;
}
prev = p2;
p2 = tmp;
}
}
if (p2) {
prev->next = p2;
}
return l1;
}
int main() {
ListNode *l1 = (ListNode*)malloc(sizeof(ListNode));
l1->val = 1;
l1->next = (ListNode*)malloc(sizeof(ListNode));
l1->next->val = 3;
l1->next->next = (ListNode*)malloc(sizeof(ListNode));
l1->next->next->val = 5;
l1->next->next->next = NULL;
ListNode *l2 = (ListNode*)malloc(sizeof(ListNode));
l2->val = 2;
l2->next = (ListNode*)malloc(sizeof(ListNode));
l2->next->val = 4;
l2->next->next = (ListNode*)malloc(sizeof(ListNode));
l2->next->next->val = 6;
l2->next->next->next = NULL;
ListNode *merged = merge(l1, l2);
printf("Merged list: ");
while (merged) {
printf("%d ", merged->val);
merged = merged->next;
}
printf("\n");
return 0;
}
```
这个算法使用了两个指针p1和p2分别指向两个链表的头结点,然后遍历两个链表,比较p1和p2的值,将较小的结点插入到结果链表中。如果p2的值比p1的值小,则将p2插入到p1之前,否则p1继续向后移动。最后,如果p2还有剩余结点,则将它们全部插入到结果链表的末尾。
阅读全文