合并链表(线性表)

合并链表(线性表)

时间: 1ms        内存:128M

描述:

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

输入:

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

输出:

10 9 8 7 6 5 4 3 2 1

示例输入:

4
7 9 10 11
4
8 12 13 14

示例输出:

14 13 12 11 10 9 8 7 

提示:

参考答案(内存最优[752]):

#include <stdio.h>
#include <stdlib.h>
typedef struct i{
	int date;
	struct i *next;
}biao;
biao *jb(int n)
{   int i;
   biao *p,*q,*head;
   head=p=(biao *)malloc(sizeof(biao));
    q=p;
	for(i=0;i<n;i++)
	{
      p=(biao *)malloc(sizeof(biao));
	  q->next=p;
	  scanf("%d",&(q->date));
	  q=p;
	}
    q->next=NULL;
	return head;
}
int main()
{  
  int n1,n2,max,min,t,i;
  biao *p1,*p2,*p3,*p4,*head,*p;
  scanf("%d",&n1);
  head=p1=jb(n1);
  p3=p1;
  scanf("%d",&n2);
  p2=jb(n2);
  while(p3->next!=NULL)
     p3=p3->next;
  p3->next=p2;
  p=p1;
  while(p1->next!=NULL)
  {
   max=min=p1->date;
   p4=p1;
   p=p1;
   while(p4!=NULL){  
	   if(p4->date>max){
		   max=p4->date;
		   p=p4;
	   }
	p4=p4->next;
   }
   t=p->date;
   p->date=p1->date;
   p1->date=t;
   p1=p1->next;
  }
  p=head;
  for(i=0;i<n1+n2;i++){
	  if(i==0)
	  printf("%d",p->date);
	  else
	  printf(" %d",p->date);
	  p=p->next;
  }
  return 0;
}

参考答案(时间最优[0]):

#include <stdio.h>
#include <stdlib.h>
typedef struct i{
	int date;
	struct i *next;
}biao;
biao *jb(int n)
{   int i;
   biao *p,*q,*head;
   head=p=(biao *)malloc(sizeof(biao));
    q=p;
	for(i=0;i<n;i++)
	{
      p=(biao *)malloc(sizeof(biao));
	  q->next=p;
	  scanf("%d",&(q->date));
	  q=p;
	}
    q->next=NULL;
	return head;
}
int main()
{  
  int n1,n2,max,min,t,i;
  biao *p1,*p2,*p3,*p4,*head,*p;
  scanf("%d",&n1);
  head=p1=jb(n1);
  p3=p1;
  scanf("%d",&n2);
  p2=jb(n2);
  while(p3->next!=NULL)
     p3=p3->next;
  p3->next=p2;
  p=p1;
  while(p1->next!=NULL)
  {
   max=min=p1->date;
   p4=p1;
   p=p1;
   while(p4!=NULL){  
	   if(p4->date>max){
		   max=p4->date;
		   p=p4;
	   }
	p4=p4->next;
   }
   t=p->date;
   p->date=p1->date;
   p1->date=t;
   p1=p1->next;
  }
  p=head;
  for(i=0;i<n1+n2;i++){
	  if(i==0)
	  printf("%d",p->date);
	  else
	  printf(" %d",p->date);
	  p=p->next;
  }
  return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注