拆分链表(线性表)

拆分链表(线性表)

时间: 1ms        内存:128M

描述:

编写一个函数将一个头指针为a的单链表A分解成两个单链表AB,其头指针分别为ab,使得A链表中含有原链表A中序号为奇数的元素,而B链表中含有原链表A中序号为偶数的元素,且保持原来的相对顺序。

输入:

输入链表长度n:6

输入数据:1 3 4 5 6 9

输出:

输出链表A:1 4 6

输出链表B:3 5 9

示例输入:

7
1 2 3 4 5 6 7

示例输出:

1 3 5 7 
2 4 6 

提示:

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

#include <stdio.h>
#include <stdlib.h>
typedef struct s
{
	int date;
	struct s *link;
}S;
S *creat(int n)
{
	S *p,*q,*head;
	head=p=q=malloc(sizeof(S));
	scanf("%d",&p->date);
	while(--n)
	{
		p=malloc(sizeof(S));
		scanf("%d",&p->date);
		q->link=p;
		q=p;
	}
	q->link=NULL;
	return head;
}
void play(S *h,int n)
{
	S *p,*q,*h1=h,*h2=h->link;
	int i;
	for(p=h1,q=h2,i=0;p!=NULL && q!=NULL && i<(n+1)/2-1;i++)
	{
		p->link=p->link->link;
		q->link=q->link->link;
		p=p->link;
		q=q->link;
	}
	if(!(n%2))
	{
		q=NULL;
		p=NULL;
	}
	else
		p->link=NULL;
	for(p=h1,i=1;i<=(n+1)/2;p=p->link,i++)
		printf("%d ",p->date);
	printf("\n");
	for(p=h2,i=1;p!=NULL;p=p->link,i++)
		printf("%d ",p->date);
	printf("\n");
}
int main()
{
	int n;
	scanf("%d",&n);
	play(creat(n),n);
	return 0;
}

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

#include <stdio.h>
#include <stdlib.h>
typedef struct s
{
	int date;
	struct s *link;
}S;
S *creat(int n)
{
	S *p,*q,*head;
	head=p=q=malloc(sizeof(S));
	scanf("%d",&p->date);
	while(--n)
	{
		p=malloc(sizeof(S));
		scanf("%d",&p->date);
		q->link=p;
		q=p;
	}
	q->link=NULL;
	return head;
}
void play(S *h,int n)
{
	S *p,*q,*h1=h,*h2=h->link;
	int i;
	for(p=h1,q=h2,i=0;p!=NULL && q!=NULL && i<(n+1)/2-1;i++)
	{
		p->link=p->link->link;
		q->link=q->link->link;
		p=p->link;
		q=q->link;
	}
	if(!(n%2))
	{
		q=NULL;
		p=NULL;
	}
	else
		p->link=NULL;
	for(p=h1,i=1;i<=(n+1)/2;p=p->link,i++)
		printf("%d ",p->date);
	printf("\n");
	for(p=h2,i=1;p!=NULL;p=p->link,i++)
		printf("%d ",p->date);
	printf("\n");
}
int main()
{
	int n;
	scanf("%d",&n);
	play(creat(n),n);
	return 0;
}

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

点赞

发表评论

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