用C语言,链表拼接:输入若干个正整数(输入-1微结束标志),建立两个已按升序排列的单向链表,头指针分别为list1、list2,把两个链表拼成一个链表,并输出新链表信息。要求自定义函数,实现将两个链表拼成一个链表,并返回拼组后的新链表。试编写相应程序。
时间: 2023-06-26 07:06:34 浏览: 118
C语言合并两个带头节点升序排列链表
以下是用 C 语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *createList() {
Node *head = NULL, *tail = NULL;
int num;
scanf("%d", &num);
while (num != -1) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = num;
newNode->next = NULL;
if (head == NULL) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
scanf("%d", &num);
}
return head;
}
Node *mergeList(Node *list1, Node *list2) {
Node *head = NULL, *tail = NULL;
while (list1 != NULL && list2 != NULL) {
Node *newNode = (Node*)malloc(sizeof(Node));
if (list1->data <= list2->data) {
newNode->data = list1->data;
list1 = list1->next;
} else {
newNode->data = list2->data;
list2 = list2->next;
}
newNode->next = NULL;
if (head == NULL) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
}
if (list1 != NULL) {
tail->next = list1;
} else {
tail->next = list2;
}
return head;
}
void printList(Node *head) {
Node *p = head;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
Node *list1 = createList();
Node *list2 = createList();
Node *mergedList = mergeList(list1, list2);
printList(mergedList);
return 0;
}
```
首先定义了一个 `Node` 结构体作为链表的节点,其中包含了一个整型数据成员 `data` 和一个指向下一个节点的指针 `next`。
然后实现了 `createList` 函数,用于创建链表。函数中用一个循环读入若干个正整数,直到读入 -1 为止。每读入一个数就创建一个新节点,并将其插入链表的尾部。
接着实现了 `mergeList` 函数,用于将两个已按升序排列的单向链表拼接成一个链表。函数中用两个指针分别指向两个链表的头节点,通过比较节点数据大小来选择将哪个节点插入新链表的尾部,直到其中一个链表被遍历完为止。最后将未被遍历完的链表直接接到新链表的尾部即可。
最后实现了 `printList` 函数,用于输出链表信息。函数中用一个指针遍历链表并输出每个节点的数据。
在 `main` 函数中,先分别创建两个已按升序排列的单向链表,然后调用 `mergeList` 函数将它们拼接成一个链表,并将拼接后的链表传递给 `printList` 函数输出。
阅读全文