1025?反轉(zhuǎn)鏈表?（25 分）
給定一個常數(shù)?K?以及一個單鏈表?L袁滥，請編寫程序?qū)?L?中每?K?個結(jié)點反轉(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?個元素不反轉(zhuǎn)。
輸入格式：
每個輸入包含 1 個測試用例翰萨。每個測試用例第 1 行給出第 1 個結(jié)點的地址脏答、結(jié)點總個數(shù)正整數(shù)?N?(≤10?5??)、以及正整數(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
#include <iostream>
#include<stdio.h>
#include<iomanip>
#include<cstring>
using namespace std;
typedef struct Node{
int add;
int num;
int next;
};
int main()
{
? ? int a=100;
? ? cout<<setw(6)<<setfill('0')<<a<<endl;
}
//改代碼是思考過程 ，把地址存為int型初澎，輸出時再補齊秸应。
樣例0，3谤狡，4是只需要一次反轉(zhuǎn)的。
#include <iostream>
#include<stdio.h>
#include<iomanip>
#include<cstring>
#include<algorithm>
using namespace std;
typedef struct Node{
int add;
int num;
int next;
};
bool compare(Node a,Node b){
? ? return (a.num<b.num);
}
bool compare2(Node a,Node b){
? ? return (a.num>b.num);
}
int main()
{
? ? int strartadd,num,revernum;
? ? int temp,j;
? ? j=0;
? ? scanf("%d %d %d",&strartadd,&num,&revernum);
? ? Node node[num];
? ? for(int i=0;i<num;i++){
? ? ? ? scanf("%d %d %d",&node[i].add,&node[i].num,&node[i].next);
? ? }
? ? ? ? if(revernum==0){
? ? for(int i=0;i<num;i++){
? ? ? cout<<setw(5)<<setfill('0')<<node[i].add<<' '<<node[i].num<<' '<<setw(5)<<setfill('0')<<node[i].next<<endl;
? ? }
? ? }
? ? temp=num/revernum;
? ? sort(node,node+num,compare);
? ? //printf("000\n");
? ? while(temp>j){
? ? sort(node+j*revernum,node+((j+1)*revernum),compare2);
? ? j++;
? ? }
? ? for(int i=0;i<num-1;i++){
? ? ? ? node[i].next=node[i+1].add;
? ? ? cout<<setw(5)<<setfill('0')<<node[i].add<<' '<<node[i].num<<' '<<setw(5)<<setfill('0')<<node[i].next<<endl;
? ? }
? cout<<setw(5)<<setfill('0')<<node[num-1].add<<' '<<node[num-1].num<<' '<<"-1"<<endl;
}
//以上是自己寫的代碼卧檐。最后錯了兩個樣例
以下是網(wǎng)上代碼：
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int main()
{
? ? int start, N, K;//起始節(jié)點地址墓懂，總結(jié)點個數(shù)，反轉(zhuǎn)的節(jié)點個數(shù)
? ? cin >> start >> N >> K;
? ? /*初始化數(shù)據(jù)*/
? ? int data[100000];//記錄對應(yīng)地址的數(shù)據(jù)
? ? int next[100000];//存儲下一節(jié)點的地址
? ? int list[100000];//表現(xiàn)節(jié)點間的先后次序
? ? for (int i = 0; i < N; i++)
? ? {
? ? ? ? int address;
? ? ? ? cin >> address;
? ? ? ? cin >> data[address] >> next[address];
? ? }
? ? /*將節(jié)點按照先后順序排列*/
? ? int sum = 0;//
? ? for (int i = 0; start != -1; i++)
? ? {
? ? ? ? list[i] = start;
? ? ? ? start = next[start];
? ? ? ? sum++;
? ? }
? ? /*反轉(zhuǎn)*/
? ? for (int i = 0; i < sum / K; i++)
? ? {
? ? ? ? reverse(list + i * K, list + (i + 1) * K);
? ? }
? ? /*輸出*/
? ? for (int i = 0; i < sum; i++)
? ? {
? ? ? ? if (i == sum - 1)
? ? ? ? ? ? printf("%05d %d -1\n", list[i], data[list[i]]);
? ? ? ? else
? ? ? ? ? ? printf("%05d %d %05d\n", list[i], data[list[i]], list[i + 1]);
? ? }
? ? system("pause");
? ? return 0;
}
