一、引言
为什么要写这篇博客呢？因为我在网上找不到我想要的答案（也可能只是我没有找到）。这学期开始学习数据结构这门课，第一个需要我们弄透彻的东西就是链表，也就是链式存储结构。PTA上的这道题，如果我仅仅是要完成题目的要求，那么我用四十多行代码就可以完成，唯一的缺点就是没有用到链式存储结构，只完成了题目的输出要求，但其实根本就没有把链表进行重排。现在CSDN上大多数都是用的这种思想，我们抛开数据结构这门课程来看，我用四十多行代码就可以搞定，而且不仅节省空间还快，正所谓大道至简。但是，既然我们是在学习数据结构这门课程，我们就不要偷懒、取巧。题目既然说了用链式的存储结构，那么就一定可以采用链式存储结构来解决，但是采用链式结构，我们事先根本不知道每个节点的地址，我们只能通过遍历来进行操作，换句话就是我们根本用不到题目中给出的address和next_address。那么接下来，我们就一步一步分析。
由于我们不去用题目中给的address和next_address，只需要将它们作为数据保存即可。那么我们定义的结构体如下：
typedef struct node{
int data;
int address;
int next_address;
struct node*next;
}node,*List;二、题目内容
给定一个单链表 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.首先说一个需要注意的点，这道题有一个坑就是会给你多余的节点，比如
| 00100 11 00000 4 99999 00100 1 12309 68237 6 98745 33218 3 00000 99999 5 68237 12309 2 33218 98745 7 98763 98763 8 66544 66544 9 44533 44533 10 -1 67809 11 -1 |
很明显，最后一行的数据是多余的，我们需要把它过滤掉，那么就需要我们开动脑筋在链表初始化的时候做一些改动。题目给出的数据有address、data、next_address，我们需要用到的就是其中的address和next_address。具体思路是这样的：我们可以先将数据存储到一个静态链表里面，再通过一个循环把数据从静态链表里面转入链表里面，这样就可以过滤掉多余节点。
int start_address,n,address,num=0;
scanf("%d %d",&start_address,&n);
//先将数据输入到静态链表里面
node a[100001];
for (int i=0;i<n;i++){
scanf("%d", &address); a[address].address=address;
scanf("%d %d",&a[address].data, &a[address].next_address);
}
//声明头节点并初始化
List head=(List)malloc(sizeof(node));
head->next=NULL;
List p=head; //p为工作指针
//循环退出条件就是当下一个节点的地址为-1，说明后面不会再有其他的节点了，这样就完成了过滤
while(start_address!=-1){
//尾插法进行链表的初始化
List s=(List)malloc(sizeof(node));
s->data=a[start_address].data;
s->address=start_address;
s->next_address=a[start_address].next_address;
s->next=NULL;
p->next=s;
p=s;
start_address=a[start_address].next_address; //静态链表中的数据后移
num++; //循环完后num就是实际节点的个数，后面会用到
}
head=head->next; //头节点变头指针2.完成链表的创建之后，我们就要思考如何将链表进行重排。不知道各位写的时候是否会有超时的问题，如果超时说明你的方法不对。比如我一开始用的是一头一尾两个工作指针来进行重排，但是每次都需要让尾指针向前移动，这就要每次都进行遍历，所以就会超时。这就迫使我们去想一种新的排序方式。这种方法就是将链表从中间断开，后半部分逆置，然后将后半部分插入前半部分，最后一个节点分奇偶单独处理，这样就完成了链表的重排。其实这种方法本质上和首尾指针的方法一样，但是链表断开、逆置（头插法）比每次让尾指针向前移动时间复杂度小太多（在大量数据的情况下）。所以下面我们就需要完成三个工作：<1>断开链表（也就是找到中间节点）<2>后半部分逆置（头插法）<3>重排链表。完成这三个工作后只需要将新的链表按照要求格式输出即可。
3.那么如何找到链表中间节点呢？在知道节点数量的前提下，我们可以用一个for循环，控制循环次数找到中间节点，这个很容易。这里我给大家另一种从网上看来的方法：快慢指针。原理就是快指针每次向后移动两个结点，慢指针每次向后移动一个结点，这样当快指针移动到表尾时，慢指针就停在中间节点。当节点个数为奇数时，慢指针恰好就指向中间节点。当节点个数为偶数时，慢指针就指向中间两个节点的第二个。这个我们在后面重排时也会分情况考虑，现在就只需要将慢指针返回即可。
List middleNode(List head){
List slow=head;
List fast=head;
while(fast&&fast->next){
slow=slow->next; //满指针每次向后移动一个节点
fast=fast->next->next; //快指针每次向后移动两个节点
}
return slow; //最后将慢指针返回
}4.得到中间节点之后，我们就可以来将后半部分进行反转了。进行反转我们用头插法即可，先生成一个新的节点，然后将后半部分按头插法插入到新的节点后面即可完成反转。具体实现如下：
List fanzhuan(List head){
List p=head; //p为工作指针
List new_head=NULL; //生成新的节点
List next=NULL; //next指针用来保存要插入节点的后面内容，防止数据丢失
while(p){
next=p->next; //先抓住后面的内容
p->next=new_head; //将节点插入新的头节点之前
new_head=p; //头节点再指向p，这样循环完成即可得到逆序
p=next; //工作指针后移
}
return new_head; //最后将新的头节点返回即可
}偶数情况下，我们从中间两个节点的第二个开始反转。奇数情况下，我们把中间节点后面的链表进行反转。如下面图中方框所示：
5.完成以上两个工作之后，我们就要进行插入工作了。我们大体的思路是分奇偶考虑，最后一个节点单独处理。题目的要求是新链表是原来链表的一尾一头，我们可以设置一个标志位，标志位等于-1的时候将前面的元素插入到后面元素的后面，当标志位等于1的时候将后面元素插入到前面元素的后面，最后单独处理最后一个节点。这就需要我们想一想在奇数、偶数的情况下这样的操作需要进行几次，方便我们得到循环的循环次数。在奇数节点的情况下需要进行num-2次，然后单独处理最后节点，偶数情况下进行num-1次然后单独处理最后节点。具体的流程可以看下面的流程图：
为什么奇数/偶数处理次数会不同，这与我们找的中间节点位置有关，在奇数/偶数的情况下，得到的中间节点是不同的。下面是具体代码：
List chongpai(List head1,int num){ //参数一是原来的顺序链表，参数二是实际节点个数
List middle=middleNode(head1); //找到中间节点middle
List head2;
//head2为反转后的后半部分链表，为什么分奇偶参见过程3、4
if(num%2!=0) head2=fanzhuan(middle->next);
if(num%2==0) head2=fanzhuan(middle);
middle->next=NULL; //这一步相当于断开链表
List p=head1;
List q=head2; //p和q是两个工作指针
List next1=NULL;
List next2=NULL; //因为涉及到修改next指针域，next1和next2用来抓住后面数据，防止数据丢失
List new_head=q; //重排后的第一个元素是原来的最后一个
int flag=-1; //flag为-1表示前面元素插入到后面元素的后面，为1则相反
//奇数情况
if(num%2!=0){
for(int i=0;i<num-2;i++,flag*=-1){
if(flag==-1){
next2=q->next;
q->next=p;
q->next_address=p->address;
q=next2;
}
if(flag==1){
next1=p->next;
p->next=q;
p->next_address=q->address;
p=next1;
}
}
p->next=middle; //如果有5个元素，那么现在的p相当于2，它的下一个节点是3（中间节点）
middle->next_address=-1;
middle->next=NULL;
}
//偶数情况
if(num%2==0){
for(int i=0;i<num-1;i++,flag*=-1){
if(flag==-1){
next2=q->next;
q->next=p;
q->next_address=p->address;
q=next2;
}
if(flag==1){
next1=p->next;
p->next=q;
p->next_address=q->address;
p=next1;
}
}
p->next=NULL; //此时的p相当于测试例子中的3，单独处理
p->next_address=-1;
}
//返回新的头指针即可
return new_head;
}6.按要求输出
这个函数非常简单，不做过多解释！
void Print(List head){
while(head){
if(head->next==NULL) printf("%05d %d -1",head->address,head->data);
else printf("%05d %d %05d\n",head->address,head->data,head->next_address);
head=head->next;
}
}四、完整代码附测试用例
#include<stdio.h>
#include<malloc.h>
typedef struct node{
int data;
int address;
int next_address;
struct node*next;
}node,*List;
List middleNode(List head){
List slow=head;
List fast=head;
while(fast&&fast->next){
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
List fanzhuan(List head){
List p=head;
List new_head=NULL;
List next=NULL;
while(p){
next=p->next;
p->next=new_head;
new_head=p;
p=next;
}
return new_head;
}
List chongpai(List head1,int num){
List middle=middleNode(head1);
List head2;
if(num%2!=0) head2=fanzhuan(middle->next);
if(num%2==0) head2=fanzhuan(middle);
middle->next=NULL;
List p=head1;
List q=head2;
List next1=NULL;
List next2=NULL;
List new_head=q;
int flag=-1;
if(num%2!=0){
for(int i=0;i<num-2;i++,flag*=-1){
if(flag==-1){
next2=q->next;
q->next=p;
q->next_address=p->address;
q=next2;
}
if(flag==1){
next1=p->next;
p->next=q;
p->next_address=q->address;
p=next1;
}
}
p->next=middle;
middle->next_address=-1;
middle->next=NULL;
}
if(num%2==0){
for(int i=0;i<num-1;i++,flag*=-1){
if(flag==-1){
next2=q->next;
q->next=p;
q->next_address=p->address;
q=next2;
}
if(flag==1){
next1=p->next;
p->next=q;
p->next_address=q->address;
p=next1;
}
}
p->next=NULL;
p->next_address=-1;
}
return new_head;
}
void Print(List head){
while(head){
if(head->next==NULL) printf("%05d %d -1",head->address,head->data);
else printf("%05d %d %05d\n",head->address,head->data,head->next_address);
head=head->next;
}
}
int main(){
int start_address,n,address,num=0;
scanf("%d %d",&start_address,&n);
node a[100001];
for (int i=0;i<n;i++){
scanf("%d", &address); a[address].address=address;
scanf("%d %d",&a[address].data, &a[address].next_address);
}
List head=(List)malloc(sizeof(node));
head->next=NULL;
List p=head;
while(start_address!=-1){
List s=(List)malloc(sizeof(node));
s->data=a[start_address].data;
s->address=start_address;
s->next_address=a[start_address].next_address;
s->next=NULL;
p->next=s;
p=s;
start_address=a[start_address].next_address;
num++;
}
head=head->next;
List new_head=chongpai(head,num);
Print(new_head);
return 0;
}
/*
00100 5
00000 4 99999
00100 1 12309
33218 3 00000
99999 5 -1
12309 2 33218
*/
/*
00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
*/
/*
00100 11
00000 4 99999
00100 1 12309
68237 6 98745
33218 3 00000
99999 5 68237
12309 2 33218
98745 7 98763
98763 8 66544
66544 9 44533
44533 10 -1
67809 11 -1
*/五、结束语
现在数据结构已经把重要的内容都讲完了，回头看，一开始觉得难的内容变得再简单不过。这道题很简单，但是它是我们学习后面内容的基础，链式结构搞不清楚，后面表、树、图会很吃力。不知道为什么，越来越喜欢这门课，虽然有时候上课听着听着就找不到北了，但是如果要是真弄懂一个存储结构、一个算法，会很有成就感。说真的，会别人不会的这种感觉会让人上瘾，推着你去学更多的东西。上次找老师检查树的实验，老师说代码风格很乱，没有层次感，这不是一个好的习惯。后来，我把代码又改了一遍，主函数中除了关键的几个点，剩下的全是函数调用，能让人一看就知道这一步是干什么，代码长度比原来小了将近20行，可读性强了太多。把代码写出来的人很多，但写得好的很少。没别的，菜就多练，别老拿现在跟以前比。最后，祝大家真正学懂数据结构!
文章出处登录后可见！
