PAT (Basic Level) Practise （中文）-1025. 反轉(zhuǎn)鏈表 (25) ??http://www.patest.cn/contests/pat-b-practise/1025

?

給定一個(gè)常數(shù)K以及一個(gè)單鏈表L，請(qǐng)編寫(xiě)程序?qū)中每K個(gè)結(jié)點(diǎn)反轉(zhuǎn)。例如：給定L為1→2→3→4→5→6，K為3，則輸出應(yīng)該為3→2→1→6→5→4；如果K為4，則輸出應(yīng)該為4→3→2→1→5→6，即最后不到K個(gè)元素不反轉(zhuǎn)。

輸入格式：

每個(gè)輸入包含1個(gè)測(cè)試用例。每個(gè)測(cè)試用例第1行給出第1個(gè)結(jié)點(diǎn)的地址、結(jié)點(diǎn)總個(gè)數(shù)正整數(shù)N(<= 10⁵)、以及正整數(shù)K(<=N)，即要求反轉(zhuǎn)的子鏈結(jié)點(diǎn)的個(gè)數(shù)。結(jié)點(diǎn)的地址是5位非負(fù)整數(shù)，NULL地址用-1表示。

接下來(lái)有N行，每行格式為：

Address Data Next

其中Address是結(jié)點(diǎn)地址，Data是該結(jié)點(diǎn)保存的整數(shù)數(shù)據(jù)，Next是下一結(jié)點(diǎn)的地址。

輸出格式：

對(duì)每個(gè)測(cè)試用例，順序輸出反轉(zhuǎn)后的鏈表，其上每個(gè)結(jié)點(diǎn)占一行，格式與輸入相同。

輸入樣例：

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

輸出樣例：

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





此題一大坑兒就是： 遇到-1則結(jié)束，不管提供的節(jié)點(diǎn)是否有剩余

 1 #include<stdio.h>
 2 
 3 int main()
 4 {
 5     int head=0,n=0,v=0;
 6     scanf("%d%d%d",&head,&n,&v);
 7     
 8     int address=0,data=0,next=0,prior=0,ppp=0;
 9     int node[100000][3]={0};// 0-prior   1-Data 2-Next  
10     for(int i=0;i<n;i++)
11     {
12         scanf("%d%d%d",&address,&data,&next);
13         node[address][1]=data;
14         node[address][2]=next;
15     }
16      
17     next=head; //修補(bǔ)前指針 
18     prior=head;
19     for(int i=0;i<n;i++)
20     {
21         node[next][0]=prior;
22         prior=next;  
23         next=node[next][2];
24         while(next<0)
25         {
26                      n=i+1;
27                      break;
28                      
29         }
30     }
31     ppp=next;//node[next][0]=prior;
32         
33         
34     prior=-1;
35     next=head;
36     if(v<=1) v=n+1;
37     for(int i=0;i<n;)
38     {
39         next=head; 
40         if(i+v<=n)
41         {
42             for(int j=i;j<i+v;j++)
43             {
44                 if(j==i) next=head;
45                 else next=node[next][2];
46             }
47      
48             head=node[next][2];
49             for(int j=i;j<i+v;j++)
50             {
51                  if(j) printf(" %05d\n",next);
52                  printf("%05d %d",next,node[next][1]);
53                   
54                  next=node[next][0];       
55             }
56         }
57         else
58         { 
59             for(int j=i;j<n;j++)
60             {
61                  if(j) printf(" %05d\n",next);
62                  printf("%05d %d",next,node[next][1]);
63                  next=node[next][2];       
64             } 
65         }
66             
67         i+=v;    
68     }
69     printf(" %d",ppp);
70     return 0;
71 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/asinlzm/p/4445206.html

總結(jié)

以上是生活随笔為你收集整理的PAT (Basic Level) Practise （中文）-1025. 反转链表 (25)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。