本文主要是介绍Reversing Linded list【数据结构测试2.1】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
PAT 1074. Reversing Linked List，作为课后题出现在数据结构MOOC上。
刚开始学数据结构，水平还差的远
，参考网上code，参考：http://tech-wonderland.net/blog/pat-1074-reversing-linked-list.html
，参考网上code，参考：http://tech-wonderland.net/blog/pat-1074-reversing-linked-list.html
路漫漫其修远兮
也是刚开始没有理解好题目意思，导致有几处感觉有难度，后来才发现是想多了。
几个需要注意的地方：
1、链表反转长度K要注意分情况讨论：<1的时候，>链表长度N的时候， =2的时候（此处要注意输入数据是多链表的时候，要修正有效链长）
2、只有1个节点的时候，输出问题
3、输入数据的K>N的时候，还是要注意重新修正有效链长，与1中提到的情况关联，否则可能会出现死循环的情况
详细讨论在代码后面：（代码为了方便自己以后看，注释较多= =）
#include "stdafx.h"
#include <fstream>
#include<vector>
#include <iostream>
#include <iomanip>
using namespace std; const int MaxSize = 100004;
int ihead;//头结点
int N,K;//node个数N，需要反转的node个数K
struct Node{int iData;int iNext;
};Node NodeList[MaxSize];//链表void doPrint(int ilisthead)//输入表头，输出整表
{while(-1 != ilisthead){if(NodeList[ilisthead].iNext == -1)//只有一个节点或者多个链表的时候只打印第一个{cout<<setw(5)<<setfill('0')<<ilisthead<<" "<<NodeList[ilisthead].iData<<" "<<"-1"<<endl;break;}cout<<setw(5)<<setfill('0')<<ilisthead<<" "<<NodeList[ilisthead].iData<<" "<<setw(5)<<setfill('0')<<NodeList[ilisthead].iNext<<endl;ilisthead = NodeList[ilisthead].iNext;//指向下个节点}
}//反转指定长度的节点(一次)
int reversK(int istart,int ik,int *phead,int *ptail)
{if(-1 == istart || ik <= 1)return -1;if(2 == ik){int node1 = istart;int node2 = NodeList[istart].iNext;NodeList[node1].iNext = NodeList[node2].iNext;//交换头尾NodeList[node2].iNext = node1;*phead = node2;//向后移动*ptail = node1;return 0;}// >=3的情况*ptail = istart;//保存表头，作为最后的表尾int node1 = istart;int node2 = NodeList[istart].iNext;int nodeTmp = -1;for(int i = 0; i < ik - 1; ++i)//反转ik个节点需要改变ik-1个连接关系{//暂存node2下个元素地址后改为指向node1nodeTmp = NodeList[node2].iNext;NodeList[node2].iNext = node1;//node1,node2同时向后移动node1 = node2;node2 = nodeTmp;}*phead = node1;//原来最后一个元素作新的表头NodeList[*ptail].iNext = node2;//新表尾指向node2,下一个元素或者NULL(所有元素处理完)//cout<<node2<<endl;return 0;
}void process(){//将整个链表反转//get the Effective Lenthgthint itemp = ihead;int iEffectiveLenth = 1;//链表有效长度while(-1 != NodeList[itemp].iNext) { ++iEffectiveLenth; itemp = NodeList[itemp].iNext; } if(K > iEffectiveLenth) { doPrint(ihead); return;} N = iEffectiveLenth;//注意！！此处细节也不可忽略，处理链表的时候需要重新设定链表的有效长度，因为在输入是多个链表的情况下有可能会出错//cout<<N<<endl;int inewhead;if(K > 1){int iheadtmp,itailtmp;int ilasttail;//记录上次反转的尾部//先反转一次，并记录翻转后的头尾reversK(ihead,K,&iheadtmp,&itailtmp);inewhead = iheadtmp;//注意！！此处inewhead是有用的，第一次反转以后，新的链表头已经产生了，即原来的链表的第K个节点！因此下面输出链表的时候要从这个新的节点开始输出！ilasttail = itailtmp;int revcount = N / K -1;//剩余反转次数for(int i = 0; i < revcount; ++i){reversK(NodeList[itailtmp].iNext,K,&iheadtmp,&itailtmp);NodeList[ilasttail].iNext = iheadtmp;//上一次反转后尾部指向此次反转完成的头(本来指向此次反转前的尾部)（不好理解的话见下面！示意图！）ilasttail = itailtmp; }}else//K<=1的时候新的表头还是原来的表头inewhead = ihead;doPrint(inewhead);//从新的表头开始输出}
int main()
{ fstream cin("a.txt");for(int i = 0; i < MaxSize; ++i)//initial the whole list{NodeList[i].iData = 0;NodeList[i].iNext = -1;}cin>>ihead>>N>>K;int iadd,idata,inext;for(int i = 0; i < N; ++i)//读入链表{cin>>iadd>>idata>>inext;NodeList[iadd].iData = idata;NodeList[iadd].iNext = inext;}process();return 0;
}关于几点注意的讨论：
1、process()函数最后那个循环里注释部分的示意图：
2、容易忽略的一个小细节，即当输入数据不止一个串的时候要及时更新有效长度，即只处理第一个串。
N = iEffectiveLenth;//此句注意，不可忽略，处理链表的时候需要重新设定链表的有效长度，因为在输入是多个链表的情况下有可能会出错（陷入死循环，配合上图和下面的讨论不难理解）测试数据：(多串情况)
00100 6 3
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 -1<pre name="code" class="cpp">for(int i = 0; i < ik - 1; ++i)//反转ik个节点需要改变ik-1个连接关系{//暂存node2下个元素地址后改为指向node1nodeTmp = NodeList[node2].iNext;NodeList[node2].iNext = node1;//node1,node2同时向后移动node1 = node2;node2 = nodeTmp;} N影响的是下面的循环次数，而下面的又调用了上面的这段函数，因此当使用最上面的数据的时候，当k=2的时候，正确的情况应该是，由于有多个链表，N需要重新设定有效长度，重新设定以后应该为2，因此，下面的程序只循环一次；
但当N不重新设定有效长度的时候，循环次数为两次，循环过两次之后的情况就是，节点1指向节点2，节点2指向-1，（由于-1的下个节点还是-1，）因此再一次循环的时候，再执行下面的语句：
nodeTmp = NodeList[node2].iNext;NodeList[node2].iNext = node1;//node1,node2同时向后移动node1 = node2;node2 = nodeTmp; 且节点2作为头结点，因此输出的时候形成死循环。
这篇关于Reversing Linded list【数据结构测试2.1】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
