用C语言编写一串代码,将两个升序的头指针型单链表合并为降序的头指针单链表,并且只能用一个函数
时间: 2023-05-27 09:03:09 浏览: 101
以下是用C语言编写的代码,实现将两个升序的头指针型单链表合并为降序的头指针单链表:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node* next;
} Node;
Node* mergeLists(Node* l1, Node* l2) {
Node* result = NULL;
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
if (l1->value < l2->value) {
result = l1;
result->next = mergeLists(l1->next, l2);
} else {
result = l2;
result->next = mergeLists(l1, l2->next);
}
return result;
}
int main() {
Node* l1 = NULL;
Node* l2 = NULL;
// Create first linked list
Node* node1 = (Node*)malloc(sizeof(Node));
node1->value = 1;
Node* node2 = (Node*)malloc(sizeof(Node));
node2->value = 3;
Node* node3 = (Node*)malloc(sizeof(Node));
node3->value = 5;
node1->next = node2;
node2->next = node3;
node3->next = NULL;
l1 = node1;
// Create second linked list
Node* node4 = (Node*)malloc(sizeof(Node));
node4->value = 2;
Node* node5 = (Node*)malloc(sizeof(Node));
node5->value = 4;
Node* node6 = (Node*)malloc(sizeof(Node));
node6->value = 6;
node4->next = node5;
node5->next = node6;
node6->next = NULL;
l2 = node4;
// Merge lists
Node* result = mergeLists(l1, l2);
// Print merged list in descending order
while (result != NULL) {
printf("%d ", result->value);
result = result->next;
}
return 0;
}
```
在代码中,我们定义了一个 `mergeLists` 函数,该函数接收两个参数 `l1` 和 `l2`,它们分别是两个升序的头指针型单链表的头结点指针。该函数的返回值是头指针型单链表的头结点指针,它代表了将两个升序的单链表合并为一个降序单链表后的结果。
函数内部的实现是经典的递归实现,我们首先对边界情况进行了处理:当两个链表中其中一个为空时,我们直接返回另一个链表的头指针。接下来,我们比较两个链表的头结点值大小,将更小的那个链表头结点作为当前链表的头结点,并将其指向递归调用 `mergeLists` 函数的返回结果,这个返回结果也是一个链表的头指针。最终,我们将这一结果返回。
在主函数中,我们创建了两个升序的单链表,并将它们传递给 `mergeLists` 函数,获取到了合并后的降序单链表的头指针。接下来,我们遍历这个新的单链表,并打印每个结点的值,以检查合并结果是否符合我们的预期。
阅读全文