PAT 1074 Reversing Linked List

在这里插入图片描述

题目的意思给出一个链表，让我们每隔K个进行一次反转，如果不足K个的，就不进行。
对于链表反转的题目，我第一时间想出来的是，原地进行逆置，不断的变化指针，但这样很麻烦，没有想出来，看题解后发现可以用数组+reverse的方法，进行每隔K个反转。
先把链表进行按顺序放到数组中，然后每隔K个对它们进行反转。
然后按照数组的顺序输出即可，当输出next指针域的时候，reverse的反转并不会改变每一个节点的next，我们可以选择输出下一个节点的address来代替next，因为节点在数组中是按顺序排列的。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <limits.h>
#include <queue>
using namespace std;
int startaddress;
int N;
int K; 
struct node
{int address;int data;int next;
}linklist[100005];
vector<node> ans;
bool cmp(node a,node b)
{if(a.data<b.data){return true;}else{return false;}
}int main()
{//ios::sync_with_stdio(0),cin.tie(0),cout.tie(cin>>startaddress>>N>>K;for(int i=1;i<=N;i++){int address;int data;int next;cin>>address>>data>>next;linklist[address].address=address;linklist[address].data=data;linklist[address].next=next;}while(startaddress!=-1){ans.push_back(linklist[startaddress]);startaddress=linklist[startaddress].next;}for(int i=0;i<=ans.size();i+=K){if(i+K<=ans.size())reverse(ans.begin()+i,ans.begin()+i+K);   }for(int i=0;i<ans.size();i++){if(i!=ans.size()-1)printf("%05d %d %05d\n",ans[i].address,ans[i].data,ans[i+1].address);elseprintf("%05d %d -1\n",ans[i].address,ans[i].data);}return 0;}