Reversing Linded list【数据结构测试2.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;
}

N = iEffectiveLenth;//此句注意，不可忽略，处理链表的时候需要重新设定链表的有效长度，因为在输入是多个链表的情况下有可能会出错（陷入死循环，配合上图和下面的讨论不难理解）

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

nodeTmp = NodeList[node2].iNext;NodeList[node2].iNext = node1;//node1,node2同时向后移动node1 = node2;node2 = nodeTmp;