链表的拆分(线性表)

链表的拆分(线性表)

时间： 1ms        内存：128M

描述：

设 Listhead为一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域NEXT组成，整数在单链表中是无序的。编一函数，将 Listhead链中结点分成一个奇数链和一个偶数链，分别由P,Q指向，每个链中的数据按由小到大排列。程序中不得使用 NEW过程申请空间。

输入：

输入长度n：9

输入数据：2 3 5 1 4 17 23 14 19

输出：

1 3 5 17 19 23

2 4 14

示例输入：

9
12 3 6 7 16 22 27 45 57

示例输出：

3 7 27 45 57 
6 12 16 22 

提示：

参考答案（内存最优[752]）：

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
	int data;
	struct node *next;
}List;

List *Create(int n)
{
	int i;
	List *head, *p1, *p;

	head = (List *)malloc(sizeof(List));
	head->next = NULL;
	p = head;
	for(i = 0; i < n; i++)
	{
		p1 = (List *)malloc(sizeof(List));
		scanf("%d", &p1->data);
		
		p1->next = p->next;
		p->next = p1;
		p = p1;
	}

	return head;
}

void Sort(List *p, int n)
{
	List *p1, *p2;
	int i, j;
	int tmp;

	p2 = p1 = p;

	for(i = 0; i < n; i++)
	{
		for(j = 0, p1 = p->next; j < n-i-1; j++)
		{
			if(p1->data > p1->next->data)
			{
				tmp = p1->data;
				p1->data = p1->next->data;
				p1->next->data = tmp;
			}
			p1 = p1->next;
		}
	}

}

int main()
{
	List *head, *p, *p1, *p2, *q1, *q2;
	int n;
	int i, j;

	scanf("%d", &n);
	head = Create(n);
	
	p = head;
	i = j = 0;
	
	Sort(p, n);

	while(p->next)
	{
		p = p->next;
		if(p->data % 2)
		{
			j++;
			if( j == 1 )
			{
				q1 = p1 = p;
			}
			else
			{
				p1->next = p;
				p1 = p;
			}
		}
		else
		{
			i++;
			if(i == 1)
			{
				q2 = p2 = p;
			}
			else
			{
				p2->next = p;
				p2 = p;
			}
		}
	}
	p2->next = NULL;
	p1->next = NULL;
	while(q1)
	{
		printf("%d ", q1->data);
		q1 = q1->next;
	}
	printf("\n");

	while(q2)
	{
		printf("%d ", q2->data);
		q2 = q2->next;
	}
	printf("\n");


	return 0;
}

参考答案（时间最优[0]）：

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
	int data;
	struct node *next;
}List;

List *Create(int n)
{
	int i;
	List *head, *p1, *p;

	head = (List *)malloc(sizeof(List));
	head->next = NULL;
	p = head;
	for(i = 0; i < n; i++)
	{
		p1 = (List *)malloc(sizeof(List));
		scanf("%d", &p1->data);
		
		p1->next = p->next;
		p->next = p1;
		p = p1;
	}

	return head;
}

void Sort(List *p, int n)
{
	List *p1, *p2;
	int i, j;
	int tmp;

	p2 = p1 = p;

	for(i = 0; i < n; i++)
	{
		for(j = 0, p1 = p->next; j < n-i-1; j++)
		{
			if(p1->data > p1->next->data)
			{
				tmp = p1->data;
				p1->data = p1->next->data;
				p1->next->data = tmp;
			}
			p1 = p1->next;
		}
	}

}

int main()
{
	List *head, *p, *p1, *p2, *q1, *q2;
	int n;
	int i, j;

	scanf("%d", &n);
	head = Create(n);
	
	p = head;
	i = j = 0;
	
	Sort(p, n);

	while(p->next)
	{
		p = p->next;
		if(p->data % 2)
		{
			j++;
			if( j == 1 )
			{
				q1 = p1 = p;
			}
			else
			{
				p1->next = p;
				p1 = p;
			}
		}
		else
		{
			i++;
			if(i == 1)
			{
				q2 = p2 = p;
			}
			else
			{
				p2->next = p;
				p2 = p;
			}
		}
	}
	p2->next = NULL;
	p1->next = NULL;
	while(q1)
	{
		printf("%d ", q1->data);
		q1 = q1->next;
	}
	printf("\n");

	while(q2)
	{
		printf("%d ", q2->data);
		q2 = q2->next;
	}
	printf("\n");


	return 0;
}

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