设有两个有序单链表,一为升序,一为降序。试用C语言编写程序,将这两个链表合并为一个有序链表。
时间: 2023-03-22 21:00:48 浏览: 145
好的,这是一个关于C语言的问题,我可以回答。以下是一种可能的实现方式:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy;
ListNode* tail = &dummy;
dummy.next = NULL;
while (l1 && l2) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
if (l1) {
tail->next = l1;
}
if (l2) {
tail->next = l2;
}
return dummy.next;
}
int main() {
// 构造升序链表
ListNode* l1 = (ListNode*)malloc(sizeof(ListNode));
l1->val = 1;
l1->next = (ListNode*)malloc(sizeof(ListNode));
l1->next->val = 2;
l1->next->next = (ListNode*)malloc(sizeof(ListNode));
l1->next->next->val = 4;
l1->next->next->next = NULL;
// 构造降序链表
ListNode* l2 = (ListNode*)malloc(sizeof(ListNode));
l2->val = 5;
l2->next = (ListNode*)malloc(sizeof(ListNode));
l2->next->val = 3;
l2->next->next = (ListNode*)malloc(sizeof(ListNode));
l2->next->next->val = 0;
l2->next->next->next = NULL;
// 合并链表
ListNode* merged = mergeTwoLists(l1, l2);
// 输出结果
while (merged) {
printf("%d ", merged->val);
merged = merged->next;
}
printf("\n");
// 释放内存
free(l1->next->next);
free(l1->next);
free(l1);
free(l2->next->next);
free(l2->next);
free(l2);
return 0;
}
```
这个程序定义了一个链表节点结构体`ListNode`,其中包含一个整数`val`和一个指向下一个节点的指针`next`。`mergeTwoLists`函数接受两个链表头节点`l1`和`l2`作为参数,返回合并后的有序链表的头节点。这个函数使用了一个虚拟头节点`dummy`和一个尾节点指针`tail`,依次比较`l1`和`l2`的当前节点的值,将较小的节点接到`tail`后面,并将对应的链表头向后移动一位,直到其中一个链表为空。最后,将剩下的链表接到`tail`后面,返回虚拟头节点的下一个节点即可。在`main`函数中,我们构造了一个升序链表和一个降序链表,调用`mergeTwoLists`函数将它们合并成一个有序链表,并输出结果。最后
阅读全文