最快合并链表(线性表)

最快合并链表(线性表)

时间: 1ms        内存:128M

描述:

知L1、L2分别为两循环单链表的头结点指针,m,n分别为L1、L2表中数据结点个数。要求设计一算法,用最快速度将两表合并成一个带头结点的循环单链表。

输入:

m=5

3 6 1 3 5

n=4.

7 10 8 4

输出:

3 6 1 3 5 7 10 8 4

示例输入:

m=7
3 5 1 3 4 6 0

n=5

5 4 8 9 5

示例输出:

3 5 1 3 4 6 0 5 4 8 9 5 

提示:

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

#include"stdio.h"
#include"stdlib.h"
struct node{
	int date;
	struct node *next;
	struct node *pre;
};
struct node *creat(struct node *head,int t){
	struct node *p1=NULL,*p2=NULL;
	int i;
	for(i=1;i<=t;i++)
	{
		p1=(struct node*)malloc(sizeof(struct node));
		scanf("%d",&p1->date);
		p1->pre=p1->next=NULL;
		if(i==1)
			head=p1;	
		if(i!=1)
		{
			p2->next=p1;
			p1->pre=p2;
		}
		p2=p1;
	}
	p1->next=0;
	return head;
}
struct node *Union(struct node *L1,struct node *L2)
{
	struct node *p1=L1,*p2=0;
	while(p1->next!=0)
		p1=p1->next;
	p2=p1;
	p2->next=L2;
	L2->pre=p2;
	p1=L2;
	while(p1->next!=0)
		p1=p1->next;
	p1->next=L1;
	L1->pre=p1;
	return L1;
}
int main(){
	struct node *L1=0,*L2=0,*temp;
	int m,n,i,t=0;
	char c1,c2;
	scanf("%c=%d",&c1,&m);
	L1=creat(L1,m);
	while(scanf("%c",&c1))
	{
		if(c1=='n')
			break;
	}
	scanf("=%d",&n);
	L2=creat(L2,n);
	temp=Union(L1,L2);
	while(1)
	{
		printf("%d",temp->date);
		t++;
		if(t!=m+n)
			printf(" ");
		else
			break;
		temp=temp->next;
	}
	
	return 0;
}

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

#include"stdio.h"
#include"stdlib.h"
struct node{
	int date;
	struct node *next;
	struct node *pre;
};
struct node *creat(struct node *head,int t){
	struct node *p1=NULL,*p2=NULL;
	int i;
	for(i=1;i<=t;i++)
	{
		p1=(struct node*)malloc(sizeof(struct node));
		scanf("%d",&p1->date);
		p1->pre=p1->next=NULL;
		if(i==1)
			head=p1;	
		if(i!=1)
		{
			p2->next=p1;
			p1->pre=p2;
		}
		p2=p1;
	}
	p1->next=0;
	return head;
}
struct node *Union(struct node *L1,struct node *L2)
{
	struct node *p1=L1,*p2=0;
	while(p1->next!=0)
		p1=p1->next;
	p2=p1;
	p2->next=L2;
	L2->pre=p2;
	p1=L2;
	while(p1->next!=0)
		p1=p1->next;
	p1->next=L1;
	L1->pre=p1;
	return L1;
}
int main(){
	struct node *L1=0,*L2=0,*temp;
	int m,n,i,t=0;
	char c1,c2;
	scanf("%c=%d",&c1,&m);
	L1=creat(L1,m);
	while(scanf("%c",&c1))
	{
		if(c1=='n')
			break;
	}
	scanf("=%d",&n);
	L2=creat(L2,n);
	temp=Union(L1,L2);
	while(1)
	{
		printf("%d",temp->date);
		t++;
		if(t!=m+n)
			printf(" ");
		else
			break;
		temp=temp->next;
	}
	
	return 0;
}

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

点赞

发表评论

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