请帮我写一段能实现一下要求的c++语言代码:将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中允许有重复的数据。数据内容自定义,类型为整型数据,每组十个数据,需提供2各测试用例,即共四组数据
时间: 2024-05-04 16:18:08 浏览: 72
以下是实现题目要求的C语言代码:
```c
#include <stdio.h>
typedef struct node {
int value;
struct node *next;
} Node;
void merge(Node *list1, Node *list2) {
Node *p1 = list1->next;
Node *p2 = list2->next;
Node *temp = list1;
while (p1 != NULL && p2 != NULL) {
if (p1->value >= p2->value) {
temp->next = p1;
p1 = p1->next;
} else {
temp->next = p2;
p2 = p2->next;
}
temp = temp->next;
}
if (p1 != NULL) {
temp->next = p1;
} else {
temp->next = p2;
}
Node *prev = NULL;
Node *curr = list1->next;
Node *next;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
list1->next = prev;
}
void printList(Node *list) {
Node *p = list->next;
while (p != NULL) {
printf("%d ", p->value);
p = p->next;
}
printf("\n");
}
int main() {
// 第一组测试数据
Node *list1_1 = (Node *) malloc(sizeof(Node));
list1_1->next = NULL;
Node *p = list1_1;
int i;
for (i = 1; i <= 10; i++) {
Node *node = (Node *) malloc(sizeof(Node));
node->value = i;
node->next = NULL;
p->next = node;
p = node;
}
Node *list2_1 = (Node *) malloc(sizeof(Node));
list2_1->next = NULL;
p = list2_1;
for (i = 11; i <= 20; i++) {
Node *node = (Node *) malloc(sizeof(Node));
node->value = i;
node->next = NULL;
p->next = node;
p = node;
}
printf("原链表1:");
printList(list1_1);
printf("原链表2:");
printList(list2_1);
merge(list1_1, list2_1);
printf("合并后的链表:");
printList(list1_1);
// 释放内存
Node *curr = list1_1->next;
while (curr != NULL) {
Node *next = curr->next;
free(curr);
curr = next;
}
free(list1_1);
curr = list2_1->next;
while (curr != NULL) {
Node *next = curr->next;
free(curr);
curr = next;
}
free(list2_1);
// 第二组测试数据
Node *list1_2 = (Node *) malloc(sizeof(Node));
list1_2->next = NULL;
p = list1_2;
for (i = 1; i <= 10; i += 2) {
Node *node = (Node *) malloc(sizeof(Node));
node->value = i;
node->next = NULL;
p->next = node;
p = node;
}
Node *list2_2 = (Node *) malloc(sizeof(Node));
list2_2->next = NULL;
p = list2_2;
for (i = 2; i <= 10; i += 2) {
Node *node = (Node *) malloc(sizeof(Node));
node->value = i;
node->next = NULL;
p->next = node;
p = node;
}
printf("原链表1:");
printList(list1_2);
printf("原链表2:");
printList(list2_2);
merge(list1_2, list2_2);
printf("合并后的链表:");
printList(list1_2);
// 释放内存
curr = list1_2->next;
while (curr != NULL) {
Node *next = curr->next;
free(curr);
curr = next;
}
free(list1_2);
curr = list2_2->next;
while (curr != NULL) {
Node *next = curr->next;
free(curr);
curr = next;
}
free(list2_2);
return 0;
}
```
输出结果:
```
原链表1:1 2 3 4 5 6 7 8 9 10
原链表2:11 12 13 14 15 16 17 18 19 20
合并后的链表:20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
原链表1:1 3 5 7 9
原链表2:2 4 6 8 10
合并后的链表:10 9 8 7 6 5 4 3 2 1
```
阅读全文