顺序合并两个非有序的链表(C语言写法)
程序员文章站
2022-06-26 11:31:25
...
题目要求:给定由整数组成的两个无序数组,根据顺序合并成一个数组。
输入要求:输入包括两行,每行由若干个由->分隔的整数组成,分别表示以最左整数为链表头,单向指向右侧节点的链表,每行输入均以 .结尾。
输出要求:输出为合并后的单向链表,由->表示其间的指针,最终指向由NULL表示的空值。在合并过程中,比较两个链表当前待合并的第一个元素,选择其中较小的那个元素放入合并后的数组。
输入格式:输入两行字符串,每行字符串由 有符号整数、->和.组成。
输出格式:输出一行字符串,表示合并后的数组。
样例输入
1->2->3.
1->0->2.
样例输出
1->1->0->2->2->3->NULL
关于这道题,考察链表的熟练程度:会打链表、并且链表之间比较来进行插入操作。
要先打好结构体:
struct node
{
int num;//存储数字
struct node * next;//指向下一个结点
};
打链表模板:
struct node * head,* p,* q;//先定义必须的指针;
head=NULL;//让头指针指向NULL,不然后面判断head没法进行。
while(scanf("%d->",&a))//输入的同时也判断输入的内容,如果是"1->"scanf返回的是1,也是true,当输入'.'的时候,scanf返回的是0,false。被留在缓冲区
{
p=(struct node *)malloc(sizeof(struct node));
p->num=a;
p->next=NULL;
if(head==NULL)
{
head=p;//第一次时候,将链表的结点地址传给head
}
else
{
q->next=p;//第二次以及以上母结点的下一个结点为p
}
q=p;//改选中的结点为下一个结点
}
那么我们可以根据这个模板,打出两个链表:
struct node * head,* p,* q,* t,* head1,* p1,* q1;
int a,b;
head=NULL;
head1=NULL;
while(scanf("%d->",&a))//这是第一个链表开始
{
p=(struct node *)malloc(sizeof(struct node));
p->num=a;
p->next=NULL;
if(head==NULL)
{
head=p;
}
else
{
q->next=p;
}
q=p;
}
getchar();//为了清除缓冲区中残留的'.',不影响到下一个
while(scanf("%d->",&b))//第二个链表开始
{
p1=(struct node *)malloc(sizeof(struct node));
p1->num=b;
p1->next=NULL;
if(head1==NULL)
{
head1=p1;
}
else
{
q1->next=p1;
}
q1=p1;
}
那么到了交换的时候了,我们先定义一个函数来专门交换两个链表之间(递归实现)
struct node * exchange(struct node *head,struct node *head1)//定义的函数返回值为head结点地址
{
if(head==NULL||head1==NULL)
{
return head==NULL?head1:head;//判断语句如果其中一个为NULL,则返回另一个
}
struct node *head3=NULL;//该值被返回,用来做索引该链表的结点。
if(head->num<=head1->num)//开始比较大小
{
head3=head;
head3->next=exchange(head->next,head1);//递归的开始
}
else
{
head3=head1;
head3->next=exchange(head,head1->next);//递归的开始
}
return head3;
}
最后返回的是一个已经排好序的链表的头结点,只要利用头结点,并且按结点循环就可以依次输出我们所需的值:
t=exchange(head,head1);//传给t
while(t->next!=NULL)
{
printf("%d->",t->num);
t=t->next;//让t按着结点链
}
printf("%d->NULL",t->num);
return 0;
总代码图:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int num;
struct node * next;
};
struct node * exchange(struct node *p,struct node *p1);
int main()
{
struct node * head,* p,* q,* t,* head1,* p1,* q1;
int a,b;
head=NULL;
head1=NULL;
while(scanf("%d->",&a))
{
p=(struct node *)malloc(sizeof(struct node));
p->num=a;
p->next=NULL;
if(head==NULL)
{
head=p;
}
else
{
q->next=p;
}
q=p;
}
getchar();
while(scanf("%d->",&b))
{
p1=(struct node *)malloc(sizeof(struct node));
p1->num=b;
p1->next=NULL;
if(head1==NULL)
{
head1=p1;
}
else
{
q1->next=p1;
}
q1=p1;
}
t=exchange(head,head1);
while(t->next!=NULL)
{
printf("%d->",t->num);
t=t->next;
}
printf("%d->NULL",t->num);
return 0;
}
struct node * exchange(struct node *head,struct node *head1)
{
if(head==NULL||head1==NULL)
{
return head==NULL?head1:head;
}
struct node *head3=NULL;
if(head->num<=head1->num)
{
head3=head;
head3->next=exchange(head->next,head1);
}
else
{
head3=head1;
head3->next=exchange(head,head1->next);
}
return head3;
}
上一篇: A1003--顺序合并两个非有序的链表
下一篇: 【链表】两个有序链表的合并