题目:
Description

(线性表)假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并要求利用原来两个单链表的结点存放归并后的单链表。

Input

输入长度n:5
输入数据:1 2 5 6 8
输入长度m:5
输入数据:3 4 7 9 10

Output

10 9 8 7 6 5 4 3 2 1

Sample Input

4
7 9 10 11
4
8 12 13 14
Sample Output

14 13 12 11 10 9 8 7 Hint

链接:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=316#problem/B

思路:先按插入法排序合并两个单向链表,然后进行倒置
代码:
#include "stdio.h"
#include "stdlib.h"
struct node
{
int num;
struct node *next;
};
int main()
{
struct node *creat(int n);
struct node *invert(struct node *head);
struct node *order(struct node *head1,struct node *head2);
void printf(struct node *head);
struct node *head1,*head2;
int n,m;
scanf("%d",&n);
head1=creat(n);
scanf("%d",&m);
head2=creat(m);
head1=order(head1,head2);
head1=invert(head1);
printf(head1);
return 0;
}
struct node *creat(int n)
{
struct node *head,*p1,*p2;
p1=p2=(struct node *)malloc(sizeof(struct node));
head=p1;
p1->next=NULL;
scanf("%d",&p1->num);
while(–n){
p2=(struct node *)malloc(sizeof(struct node));
scanf("%d",&p2->num);
p2->next=NULL;
p1->next=p2;
p1=p2;
}
return head;
}
struct node *order(struct node *head1,struct node *head2)
{
struct node *s,*p1,*p2,*temp;
p1=head1;
p2=head2;
if(p1>p2)
{
p1=head2;
p2=head1;
}
while(p2!=NULL)
{
if(p1->next==NULL)
{
p1->next=p2;
break;
}
if(p2->num next->num)
{
s=p1->next;
temp=p2->next;
p2->next=p1->next;
p1->next=p2;
p2=temp;
p1=s;
}
else
p1=p1->next;
}
return head1;
}
struct node *invert(struct node *head)
{
struct node *p,*q,*temp;
p=head;
q=p->next;
p->next=NULL;
temp=q->next;
while(temp!=NULL)
{
temp=q->next;
q->next=p;
p=q;
q=temp;
}
return p;
}
void printf(struct node *head)
{
struct node *temp;
temp=head;
while(temp!=NULL)
{
printf("%d ",temp->num);
temp=temp->next;
}
}
提示:
之前是先将两个链表链接了起来,然后按冒泡,选择,等方法排序,交换其中值域,后来,才发现,这样的时间复杂度还是很高,与用数组没有区别,才换的这种方法。

发表评论

电子邮件地址不会被公开。

Post Navigation