输入2个空或者非空升序单链表,合并成1个升序单链表并打印,元素值为非负整形数据,链表带头结点 C语言实现
时间: 2024-03-02 08:48:58 浏览: 26
好的,我可以帮你实现这个功能。以下是 C 语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode *dummy = (ListNode*)malloc(sizeof(ListNode));
ListNode *cur = dummy;
while (l1 && l2) {
if (l1->val <= l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return dummy->next;
}
void printList(ListNode *head) {
ListNode *cur = head->next;
while (cur) {
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
}
int main() {
ListNode *l1 = (ListNode*)malloc(sizeof(ListNode));
l1->next = NULL;
ListNode *l2 = (ListNode*)malloc(sizeof(ListNode));
l2->next = NULL;
// 将 l1 和 l2 各自初始化为升序单链表
int n1, n2;
printf("请输入 l1 中元素的个数:");
scanf("%d", &n1);
printf("请输入 l1 中的元素(升序):");
for (int i = 0; i < n1; i++) {
int val;
scanf("%d", &val);
ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = val;
newNode->next = NULL;
ListNode *cur = l1;
while (cur->next && cur->next->val <= val) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
}
printf("请输入 l2 中元素的个数:");
scanf("%d", &n2);
printf("请输入 l2 中的元素(升序):");
for (int i = 0; i < n2; i++) {
int val;
scanf("%d", &val);
ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = val;
newNode->next = NULL;
ListNode *cur = l2;
while (cur->next && cur->next->val <= val) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
}
ListNode *mergedList = merge(l1->next, l2->next);
printf("合并后的单链表为:");
printList(mergedList);
return 0;
}
```
这段代码中,我们使用了归并排序的思想,将两个升序单链表合并成一个升序单链表。具体来说,我们使用了一个哑节点 dummy 来表示合并后的链表,然后使用双指针 l1 和 l2 分别指向两个链表的头节点,比较 l1 和 l2 的值的大小,将值较小的节点插入到合并后的链表中。最后,我们将剩余的节点全部接到合并后的链表的末尾即可。