PAT甲级-1074 Reversing Linked List

题目

题目大意

给一个链表的头结点和总节点个数，以及k。每k个节点的链表都要翻转。

思路

链表可以用一个结构体数组来存储，先遍历一遍，过滤掉不在链表中的节点。然后将过滤好的节点放入res数组中，每k个元素用一次reverse()，最后再输出，注意要格式化输出。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;struct node{int ads;int data;int next;
}v[100000];
int s, n, k;int main(){cin >> s >> n >> k;for (int i = 0; i < n; i++){int ads;cin >> ads;v[ads].ads = ads;cin >> v[ads].data >> v[ads].next;}vector<node> res;for (int i = s; i != -1; i = v[i].next){res.push_back(v[i]);}if ((int)res.size() >= k){for (int i = 0; i + k <= (int)res.size(); i+=k){reverse(res.begin() + i, res.begin() + i + k);}}for (int i = 0; i < (int)res.size(); i++){printf("%05d %d ", res[i].ads, res[i].data);if (i != (int)res.size() - 1){printf("%05d\n", res[i + 1].ads);}else{cout << "-1" << endl;}}return 0;
}