PTA重排链表_给定一个单链表 l1→l2→ →ln 1→ln,请编写程序将链表重新排列为 l3→

PTA重排链表

给定一个单链表 L1​→L2​→⋯→Ln−1​→Ln​，请编写程序将链表重新排列为 Ln​→L1​→Ln−1​→L2​→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤105)。结点的地址是5位非负整数，NULL地址用−1表示。

接下来有N行，每行格式为：

Address Data Next

其中Address是结点地址；Data是该结点保存的数据，为不超过105的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出格式：

对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

结尾无空行

输出样例：

68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1

结尾无空行

思路：

  本题排序不难，主要是需要考虑题目的用时问题，结点数量接近十万，如果按照常规方法进行排序一定会超时，因此我们需要解决的就是在短时间内对数据进行排序，首先按地址位置进行顺序排序，再按题目要求排序

  我们可以使用结构体数组，将结点地址当作数组下标进行存储，而后通过头结点查找到结构体数组中的下一结点的地址，以“-1”作为查找终止标志，并将查找到的地址存储到另一个整型数组中。查找完成后整型数组中就是以及按照排序好的地址，，避免了进行遍历。

  将数据进行顺序排好后，之后只需要将其按照Ln​→L1​→Ln−1​→L2​→⋯排序好即可

实现：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Linklist{
	int data;
	int next; 
}Link[100500];
int main()
{
	int address,digit,nextaddress;
	int head,N;
	int sort[100000],flag[100000];
	int k=0,t=0,v;
	scanf("%d %d",&head,&N);
	for(int i=0;i<N;i++)
	{
		scanf("%d %d %d",&address,&digit,&nextaddress);
		Link[address].data=digit;
		Link[address].next=nextaddress;
	}
	while(head!=-1)
	{
		sort[k++]=head;//将地址存储在整型地址
		head=Link[head].next;//由于存储时将地址当作下标存储，因此查找时使用地址查找即可快速知道 下一地址。
	}
	t=k;
	k=0;
	for(int i=0,j=t-1;i<=j;)
	{
		if(i==j)
		{
			flag[k]=sort[i];
			break;
		}
		else
		{
			flag[k++]=sort[j--];
			flag[k++]=sort[i++];
		}
	}
	for(int i=0;i<t-1;i++)
	{
		printf("%05d %d %05d\n",flag[i],Link[flag[i]],flag[i+1]);
		v=i;
	}
	v++;
	printf("%d %d -1\n",flag[v],Link[flag[v]]);
	return 0;	
} 
 
 
 

作者