題目信息
給定一個常數(shù)K以及一個單鏈表L，請編寫程序?qū)中每K個結(jié)點反轉(zhuǎn)怨酝。例如：給定L為1→2→3→4→5→6傀缩，K為3，則輸出應該為3→2→1→6→5→4农猬；如果K為4赡艰，則輸出應該為4→3→2→1→5→6，即最后不到K個元素不反轉(zhuǎn)斤葱。
輸入格式：
每個輸入包含1個測試用例慷垮。每個測試用例第1行給出第1個結(jié)點的地址揖闸、結(jié)點總個數(shù)正整數(shù)N(<= 105)、以及正整數(shù)K(<=N)料身，即要求反轉(zhuǎn)的子鏈結(jié)點的個數(shù)汤纸。結(jié)點的地址是5位非負整數(shù)，NULL地址用-1表示惯驼。
接下來有N行蹲嚣，每行格式為：
Address Data Next
其中Address是結(jié)點地址，Data是該結(jié)點保存的整數(shù)數(shù)據(jù)祟牲，Next是下一結(jié)點的地址隙畜。
輸出格式：
對每個測試用例，順序輸出反轉(zhuǎn)后的鏈表说贝，其上每個結(jié)點占一行议惰，格式與輸入相同。
輸入樣例：
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)棧乡恕；
(2)Algorithm頭文件里的reverse函數(shù)言询。
棧比較適用于整體逆轉(zhuǎn)，但此題有一個向后指針傲宜，如果把它也存于結(jié)構(gòu)體中运杭，則之后會麻煩許多。且此題應注意輸入的結(jié)點不一定全都存在于鏈表中函卒，故棧不合適辆憔。
代碼(柳神)
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int first, k, n, temp;
cin >> first >> n >> k;
int data[100005], next[100005], list[100005];
for (int i = 0; i < n; i++) {
cin >> temp;//temp表示地址
cin >> data[temp] >> next[temp];//data[temp]表示此地址對應的數(shù)
}
int sum = 0;//不一定所有的輸入的結(jié)點都是有用的，加個計數(shù)器
while (first != -1) {//list里只存放結(jié)點地址
list[sum++] = first;
first = next[first];
}
for (int i = 0; i < (sum - sum % k); i += k)
reverse(begin(list) + i, begin(list) + i + k);
for (int i = 0; i < sum - 1; i++)
printf("%05d %d %05d\n", list[i], data[list[i]], list[i + 1]);
printf("%05d %d -1", list[sum - 1], data[list[sum - 1]]);
return 0;
}
測試結(jié)果
心得
果然报嵌，看別人的代碼虱咧，如同看別人寫字，進步最快锚国。
