C语言代码实现:设有两个带头结点的单链表已按元素值递增次序排好,试编写算法,将这两个单链表归并为一个按元素值递减次序排列的单链表,要求只能利用原来两个单链表的结点进行归并。
时间: 2024-05-14 09:13:12 浏览: 112
数据结构与算法 c++实现 两个单链表合并为一个单链表,两个表的元素交错排列,新表用原表结点的内存空间 按元素序列的奇偶分割单
5星 · 资源好评率100%
这是一道关于算法的问题,可以直接回答。我们可以从两个单链表的头结点开始比较元素值的大小,将较小的结点插入新的单链表的头部,最终得到递减的单链表。具体实现可以参考以下C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int data;
struct Node* next;
}Node;
// 合并两个单链表,并返回新的单链表头结点
Node* merge(Node* head1, Node* head2){
Node* head = (Node*)malloc(sizeof(Node));
head->next = NULL;
while(head1 && head2){
if(head1->data <= head2->data){
Node* temp = head1->next; // 保存head1的下一个结点
head1->next = head->next;
head->next = head1;
head1 = temp;
}
else{
Node* temp = head2->next; // 保存head2的下一个结点
head2->next = head->next;
head->next = head2;
head2 = temp;
}
}
if(head1){ // 将剩余结点插入
head1->next = head->next;
head->next = head1;
}
if(head2){
head2->next = head->next;
head->next = head2;
}
Node* result = head->next;
free(head); // 释放头结点
return result;
}
// 创建单链表并返回头结点
Node* create(int arr[], int size){
Node* head = (Node*)malloc(sizeof(Node));
head->next = NULL;
Node* p = head;
for(int i = 0; i < size; i++){
Node* node = (Node*)malloc(sizeof(Node));
node->data = arr[i];
node->next = NULL;
p->next = node;
p = node;
}
return head->next;
}
// 打印单链表
void print(Node* head){
while(head){
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main(){
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 4, 6, 8};
Node* head1 = create(arr1, 4);
Node* head2 = create(arr2, 4);
print(head1);
print(head2);
Node* result = merge(head1, head2);
print(result);
return 0;
}
```
阅读全文