PTA basic 1025 反转链表 (25 分) c语言实现(gcc)

  1 //初步思路声明链表,然后按照头插法插入结点,当index+k<=n的时候,原地翻转index到index+k-1的结点,temp指针指向index的指针指向
  2 
  3 //提交后检测点5超时,显然是给出了极限条件,即当数据足够多的时候,遍历算法的效率急速下降,所要用到链表和指针来解决问题
  4 
  5 //遍历的方法会超时,用静态结构数组存储数据,使用下标作为指针模拟链表,进行链表的局部翻转,然后输出翻转后的结果
  6 
  7 //关于局部翻转的算法
  8 //核心思想
  9 //首先用三个指针来记录翻转前一个结点地址pre,后一个结点地址next以及当前节点地址current,然后就是处理子链首尾的连接
 10 //因为翻转后链表的首地址会发生变化,因此需要单独记录链表的首地址,这里用一次单独的循环来记录,结束后产生的子链首地址就是链表的首地址
 11 //题目给出的测试用例中,如果剩余子链不够k个,就不需要翻转,所以还要考虑到剩余结点的连接
 12 
 13 //第一次提交测试034通过,百度看别人写的代码 1.所给数据可能存在无效结点(测试点6通过)
 14 
 15 //第二次提交 使用静态链表方式重写了代码,测试点0246通过
 16 
 17 //第三次提交 制作了图解的链表算法过程 并且修正了多个子链表翻转时候的边界条件,检测点023456通过
 18 
 19 //最后一次提交通过
 20 
 21 //检测点1正好有N=m*K个子串需要翻转
 22 
 23 //检测点0 2 4 6 只有有1个子串,且N>K需要翻转的时候
 24 
 25 //检测点 3 5 有m个子串需要翻转且N>m*K
 26 
 27 //测试用例1
 28 //00100 12 4
 29 //00000 4 99999
 30 //00100 1 12309
 31 //68237 6 34257
 32 //33218 3 00000
 33 //99999 5 68237
 34 //12309 2 33218
 35 //34257 7 12922
 36 //12922 8 98122
 37 //98122 9 13812
 38 //13812 10 23721
 39 //23721 11 12371
 40 //12371 12 -1
 41 
 42 //测试用例2
 43 //00100 12 4
 44 //00000 4 99999
 45 //00100 1 12309
 46 //68237 6 34257
 47 //33218 3 00000
 48 //99999 5 68237
 49 //12309 2 33218
 50 //34257 7 12922
 51 //12922 8 98122
 52 //98122 9 13812
 53 //13812 10 23721
 54 //23721 11 12371
 55 //12371 12 18271
 56 //18271 13 -1
 57 
 58 
 59 #include "stdio.h"
 60 #include "stdlib.h"
 61 #include "string.h"
 62 
 63 typedef struct protoTypeNode{
 64     //地址直接用数组下标存储 ,使用的是静态结构体数组,原理和链表一样,但是题目已经给定了数据的地址,没办法使用动态链表来存储固定地址尤其是地址为0的数据,
 65     int data;
 66     int next;
 67 } node;
 68 
 69 //翻转链表核心算法
 70 int reverse(node *linkListPointer,int head,int n,int k){
 71     node *lp=linkListPointer;//链表指针
 72     int pre=0,current=0,next=0,nexthead,j=0,rear=0,repeatTimes,i;
 73     
 74     //pre用于记录需要翻转的结点的前一个结点地址
 75     //current当前翻转结点的地址
 76     //next下一个需要翻转结点的地址
 77     //nexthead下一个子链的首结点
 78     //rear子链翻转后的尾结点(即未翻转的子链的头结点)
 79     //repeatTime有多少个子链需要翻转
 80     //remainList需要翻转的子链全部翻转后是否还剩下结点
 81     
 82     pre=head;//指向未翻转的子链表的头结点
 83     current=lp[head].next;//指向头结点的下一跳结点,同时也是准备翻转的结点,准备用于翻转指向原局部头结点
 84     next=lp[current].next;//保存翻转结点的下一跳结点
 85     for(i=0;i<k-1;i++){//第一个元素的下一跳指针需要单独处理,所以重复k-1次
 86         lp[current].next=pre;//前一个元素的地址pre存入current指向的结点的下一跳指针中
 87         pre=current;//pre current next前移一位
 88         current=next;
 89         next=lp[next].next;
 90     }
 91     rear=head;//原局部头结点成为翻转后的尾结点
 92     head=pre;//局部翻转后,生成新的链表表头结点
 93     //翻转剩下的子链
 94     repeatTimes=n/k;//需要翻转多少个子链
 95     for(j=0;j<repeatTimes-1;j++){
 96         nexthead=pre=current;//更新子链头结点 //pre current next前移一位
 97         current=lp[nexthead].next;
 98         next=lp[current].next;
 99         for(i=0;i<k-1;i++){
100             lp[current].next=pre;//将前一个结点的地址存入当前翻转节点的next指针中
101             pre=current;//pre current next前移一位
102             current=next;
103             next=lp[next].next;
104         }
105         lp[rear].next=pre;//使 上一个翻转子链表的尾结点的指针指向当前 翻转子链表的新头结点
106         rear=nexthead;//当前子链表的局部头结点成为翻转后的尾结点
107     }
108     lp[rear].next=current;//翻转后的子链尾结点指向剩余子链的首结点
109     return head;
110 }
111 
112 //统计有效结点
113 int countList(node *lp,int head){
114     int count=0,current=head;
115     while(lp[current].next!=-1){
116         current=lp[current].next;
117         count++;
118     }
119     return count+1;
120 }
121 
122 //按序打印链表
123 void printList(node *lp,int head,int count){
124     int current=head,i;
125     //    printf("\n");
126     for(i=0;i<count-1;i++){
127         printf("%05d %d %05d\n",current,lp[current].data,lp[current].next);
128         current=lp[current].next;
129     }
130     printf("%05d %d %d\n",current,lp[current].data,lp[current].next);
131 }
132 
133 int main(){
134     int head=0,i,n=0,k=0,count,address,data,next,newhead;
135     scanf("%d %d %d",&head,&n,&k);
136     node linkList[100000];//N<=10^5
137     for(i=0;i<n;i++){
138         scanf("%d %d %d",&address,&data,&next);
139         linkList[address].data=data;
140         linkList[address].next=next;
141     }
142     count=countList(linkList,head);
143     newhead=reverse(linkList, head, count, k);
144     printList(linkList, newhead, count);
145     
146     return 0;
147 }