【PTA Data Structures and Algorithms (English)】7-2 Reversing Linked List

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10
5
) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next
where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

题意：

给你一个链表和一个数K，然后你需要做的就是每K个节点作为一组进行反向，最后输出操作完之后的链表

思路：

直接大模拟，STL用起来就完事，不用考虑复杂度，下面看代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
map<string,int> mp;
string invmp[N];
int cnt = 0;
struct node{string a,c;int b;
}Node[N];
struct Edge{int da;int next;
}da[N];
struct ttt{string l,r;int da;
};
int main(){int n,k;string root;ios::sync_with_stdio(false);cin.tie(0);cin>>root>>n>>k;mp[root] = ++cnt;invmp[cnt] = root;for(int i=1;i<=n;i++) da[i].next = 0;for(int i=1;i<=n;i++){cin>>Node[i].a>>Node[i].b>>Node[i].c;if(!mp[Node[i].a]) mp[Node[i].a] = ++cnt,invmp[cnt] = Node[i].a;if(!mp[Node[i].c]) mp[Node[i].c] = ++cnt,invmp[cnt] = Node[i].c;if(Node[i].c == "-1") mp[Node[i].c] = 0;da[mp[Node[i].a]].next = mp[Node[i].c];da[mp[Node[i].a]].da = Node[i].b;}invmp[0] = "-1";int p = mp[root];vector<ttt> ans;while(p != 0){vector<ttt> a;for(int i=1;i<=k;i++){if(p == 0){for(auto t : a) ans.push_back(t);for(int i=0;i<ans.size()-1;i++) ans[i].r = ans[i+1].l;ans[ans.size()-1].r = "-1";for(auto t : ans){cout<<t.l<<" "<<t.da<<" "<<t.r<<"\n";} return 0;}ttt t = {invmp[p],invmp[da[p].next],da[p].da};a.push_back(t);p = da[p].next;
//			cout<<invmp[p]<<" dasf\n";}reverse(a.begin(),a.end());for(auto t : a) ans.push_back(t);}for(int i=0;i<ans.size()-1;i++) ans[i].r = ans[i+1].l;ans[ans.size()-1].r = "-1";for(auto t : ans){cout<<t.l<<" "<<t.da<<" "<<t.r<<"\n";}return 0;
}