PAT乙級—1025. 反轉連結串列 (25)-native

NO IMAGE

給定一個常數K以及一個單連結串列L,請編寫程式將L中每K個結點反轉。例如:給定L為1→2→3→4→5→6,K為3,則輸出應該為3→2→1→6→5→4;如果K為4,則輸出應該為4→3→2→1→5→6,即最後不到K個元素不反轉。

輸入格式:

每個輸入包含1個測試用例。每個測試用例第1行給出第1個結點的地址、結點總個數正整數N(<= 105)、以及正整數K(<=N),即要求反轉的子鏈結點的個數。結點的地址是5位非負整數,NULL地址用-1表示。

接下來有N行,每行格式為:

Address Data Next

其中Address是結點地址,Data是該結點儲存的整數資料,Next是下一結點的地址。

輸出格式:

對每個測試用例,順序輸出反轉後的連結串列,其上每個結點佔一行,格式與輸入相同。

輸入樣例:
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、 然後這裡用一個vector來作為一個連結串列,因為再宣告陣列的話記憶體會爆掉,所以說vector會好一點,這裡按地址尋找到節點,將他們串起來。

3、 最後我們再用一個vector來儲存反轉後的連結串列,用迴圈將除了最後一個節點的next修改為他們下一個節點的address即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
struct Node{
int address;
int data;
int next; 
};
int main(){
int N,first,K;
vector<Node> shunxu;
vector<Node> reverse;
cin>>first>>N>>K;
Node n;
Node addr[100000];      //連結串列陣列 
for(int i=0;i<N;i  ){
cin>>n.address>>n.data>>n.next;
addr[n.address]=n;  //將節點賦值到相應下標的位置 
}
int nextaddress=first;   
while (nextaddress != -1){  //通過next作為下標尋找元素,新增到vector中,更新next繼續尋找 
shunxu.push_back(addr[nextaddress]); 
nextaddress = addr[nextaddress].next;
}
int size=shunxu.size(); //輸入的節點可能有些不在連結串列中,記錄下連結串列的長度 
int temp=K-1;
while(temp<size){       //反轉連結串列,每次翻轉K個,不足K個不反轉並退出迴圈 
for(int i=temp;i>temp-K;i--){
reverse.push_back(shunxu[i]);
}
temp =K;
}
for(int i=temp-K 1;i<size;i  )//將最後沒有反轉的,複製到反轉之後的連結串列 
reverse.push_back(shunxu[i]);
for(int i=0;i<size-1;i  ){      //修改他們的next,改為下一個元素的address 
reverse[i].next=reverse[i 1].address;
printf("%05d %d %05d\n",reverse[i].address,reverse[i].data,reverse[i].next);  
}
printf("%05d %d %d\n",reverse[size-1].address,reverse[size-1].data,-1);
return 0;
}

題目連結:

https://www.patest.cn/contests/pat-b-practise/1025