1. 假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并要求利用原来两个单链表的结点存放归并后的单链表。(扩展:可以考虑再用顺序存储结构进行实现) 用C语言
时间: 2024-09-17 18:06:23 浏览: 46
在C语言中,我们可以创建一个归并两个递增排序链表并按递减次序返回的函数。首先,我们需要定义链表节点结构体,并提供合并链表的辅助函数。这里是一个简单的示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 链表节点结构体
typedef struct ListNode {
int val; // 节点值
struct ListNode* next; // 指向下一个节点的指针
} ListNode;
// 归并两个递增链表的函数
ListNode* mergeSortedLists(ListNode* list1, ListNode* list2) {
if (!list1) return list2;
if (!list2) return list1;
// 定义一个新的头节点
ListNode* mergedList = (val1 > val2) ? list1 : list2;
list1 = (val1 > val2) ? list1->next : list1;
list2 = (val1 > val2) ? list2->next : list2->next;
mergedList->next = mergeSortedLists(list1, list2);
return mergedList;
}
// 助手函数,用于打印链表
void printList(ListNode* head) {
while (head) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
int main() {
// 创建测试链表
ListNode* list1 = malloc(sizeof(ListNode));
list1->val = 5;
list1->next = malloc(sizeof(ListNode));
list1->next->val = 8;
list1->next->next = NULL;
ListNode* list2 = malloc(sizeof(ListNode));
list2->val = 4;
list2->next = malloc(sizeof(ListNode));
list2->next->val = 6;
list2->next->next = NULL;
// 合并并打印结果
ListNode* mergedList = mergeSortedLists(list1, list2);
printList(mergedList);
return 0;
}
```
这个程序会创建两个递增链表:`5 -> 8` 和 `4 -> 6`,然后通过`mergeSortedLists`函数将它们合并成递减顺序:`8 -> 6 -> 5 -> 4`。如果要用顺序存储结构(数组),你可以先将其转换为链表后再进行归并操作。
阅读全文