題目鏈接：點擊查看

題目大意：初始時給出一條長度為n的鏈表，要求從頭開始每k位翻轉一次，最后剩下的若不足k位，則保持原順序，如：

1->2->3->4->5->6，若k為3，答案為3->2->1->6->5->4，若k為4，答案為4->3->2->1->5->6

需要按照要求翻轉并輸出，輸出格式為：當前地址? 儲存內容? 下一個地址，若當前地址為最后一個地址，則下一個地址輸出-1

題目分析：一道比簡單稍微難了一點的模擬題，不過我第一次做沒有什么比較好的思路。。甚至連暴力都沒想出來該怎么寫，主要是一開始就想模擬一個鏈表將前后的地址都串聯起來，但到了這里，卻不知道該怎么翻轉了，如果直接暴力遍歷的話顯得略微麻煩，所以就陷入了思維定式中。。

這個題目還是比較良心的，因為他給出的數組地址一定是一個五位數，那么我們就可以直接開數組模擬一下鏈表即可，儲存內容只需要儲存當前所需要保存的數據，還有下一個節點的地址（數組下標）即可，這樣在我們建立完初始的鏈表后，再用一個輔助數組記錄一下該鏈表初始情況下，每個地址的相對位置，接下來我們就可以直接用reverse函數翻轉每k個區間了，最后按照新的順序輸出即可，記得特判一下最后一位

感覺這個模擬題還是有點意思的，所以寫個博客記錄一下做法，畢竟平時做題的話鏈表類的題目接觸的還是比較少的，所以在做這個模擬題的時候就有點略顯吃力

上代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<deque> #define Pi acos(-1.0) using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;struct Node {int data;int next; }a[N];//模擬鏈表int b[N];//輔助數組int cnt=0;int main() { // freopen("input.txt","r",stdin);int head,n,k; scanf("%d%d%d",&head,&n,&k);for(int i=1;i<=n;i++){int d,ad,ne;scanf("%d%d%d",&ad,&d,&ne);a[ad].next=ne;a[ad].data=d;}for(int i=head;i!=-1;i=a[i].next)b[cnt++]=i;for(int i=0;i+k<=cnt;i+=k)//巧用reverse函數reverse(b+i,b+i+k);for(int i=0;i<cnt;i++){if(i!=cnt-1)printf("%05d %d %05d\n",b[i],a[b[i]].data,b[i+1]);elseprintf("%05d %d %d\n",b[i],a[b[i]].data,-1);}return 0; }

?

總結

以上是生活随笔為你收集整理的PAT (Basic Level) - 1025 反转链表(模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。