分别输入两个有序的整数序列(分别包含M和N个数据),建立两个有序的单链表,将这两个有序单链表合并成为一个有序单链表,并依次输出合并后的单链表数据。根据以上题目要求用c语言编写程序。
时间: 2023-11-21 08:54:17 浏览: 182
两个有序链表序列的合并_C语言_
5星 · 资源好评率100%
这道题目要求我们输入两个有序的整数序列,建立两个有序的单链表,将这两个有序单链表合并成为一个有序单链表,并依次输出合并后的单链表数据。具体实现可以按照以下步骤进行:
1. 定义两个链表头指针l1和l2,分别指向两个有序单链表的头结点。
2. 定义一个新的链表头指针head,初始值为NULL。
3. 定义一个指针p,初始值为NULL。
4. 用while循环遍历两个链表,比较l1和l2指向的节点的值的大小,将较小的节点插入到新链表head的尾部。
5. 如果l1或l2有一个链表已经遍历完了,将另一个链表剩余的节点直接插入到新链表head的尾部。
6. 输出新链表head中的数据。
以下是C语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *head = NULL, *p = NULL;
while (l1 && l2) {
if (l1->val < l2->val) {
if (!head) {
head = p = l1;
} else {
p->next = l1;
p = p->next;
}
l1 = l1->next;
} else {
if (!head) {
head = p = l2;
} else {
p->next = l2;
p = p->next;
}
l2 = l2->next;
}
}
if (l1) {
if (!head) {
head = l1;
} else {
p->next = l1;
}
}
if (l2) {
if (!head) {
head = l2;
} else {
p->next = l2;
}
}
return head;
}
int main() {
int m, n, i, x;
ListNode *l1 = NULL, *l2 = NULL, *p;
scanf("%d", &m);
for (i = 0; i < m; i++) {
scanf("%d", &x);
if (!l1) {
l1 = p = (ListNode*)malloc(sizeof(ListNode));
} else {
p->next = (ListNode*)malloc(sizeof(ListNode));
p = p->next;
}
p->val = x;
p->next = NULL;
}
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &x);
if (!l2) {
l2 = p = (ListNode*)malloc(sizeof(ListNode));
} else {
p->next = (ListNode*)malloc(sizeof(ListNode));
p = p->next;
}
p->val = x;
p->next = NULL;
}
ListNode *head = mergeTwoLists(l1, l2);
while (head) {
printf("%d ", head->val);
head = head->next;
}
return 0;
}
```
阅读全文