逆转链表-pta02-线性结构3 Reversing Linked List

题目链接 题目难点分析 1.链表结点如何逆转 用三个指针new_head、old_head,tmp。之所以要用三个，是因为除了逆转的两个结点外，还需要保存下一个待逆转的结点，不保存的话逆转之后就找不到了。 另外因为不是N个结点全部逆转，而是要一次逆转K个，所以需要保存上一次逆转之后的尾结点LastRear和这一次逆转之后的尾结点rear。需要把lastRear的指针指向当前逆转好的序列的头结点。 2.如何计算有用的结点个数 我这儿多用了一个空的头结点，用unit[MAXN-1]来表示，从头结点开始计数，直到遇到-1（NULL），停止计数，则得到有用的结点数。 3.细节处理 这道题需要很认真的写，一不注意就容易出错。我的代码 #include<stdio.h> #define MAXN 100001 struct Node{ int data; int next; }; struct Node unit[MAXN]; //打印链表 void printAll() { int addre = unit[MAXN-1].next; while(unit[addre].next != -1) { printf("d %d d\n",addre,unit[addre].data,unit[addre].next); addre = unit[addre].next; } printf("d %d %d\n",addre,unit[addre].data,unit[addre].next); } //计算有用的结点数 int countUse() { int count = 1; int addre = unit[MAXN-1].next; while(unit[addre].next != -1) { //printf("d %d d\n",addre,unit[addre].data,unit[addre].next); count++; addre = unit[addre].next; } return count; } int main() { //freopen("test.txt","r",stdin); //printf("重定向成功\n"); int head,N,K; int addr,data,next; scanf("%d%d%d",&head,&N,&K); int i; for(i=0; i<N; i++) { scanf("%d%d%d",&addr,&data,&next); unit[addr].data = data; unit[addr].next = next; //printf("d %d d\n",addr,unit[addr].data,unit[addr].next); } unit[MAXN-1].next = head; //unit[MAXN-1]为表头空结点 //printAll(N); //链表逆转 int reverseTime = countUse()/K; int new_head,old_head,tmp,lastRear,rear; lastRear = MAXN-1; for(i=0; i<reverseTime; i++) { int cnt = 1; new_head = unit[lastRear].next; rear = new_head; old_head = unit[new_head].next; while(cnt<K) { tmp = unit[old_head].next; unit[old_head].next = new_head; cnt++; new_head = old_head; old_head = tmp; //printf("%d %d\n",unit[new_head].data,unit[old_head].data); //printAll(N); } unit[lastRear].next = new_head; unit[rear].next = old_head; lastRear = rear; } //printf("计数：%d\n",countUse()); printAll(); }