02-线性结构3 Reversing Linked List（25 point(s)）
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 (≤105) 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. Sample Input:
00100 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218
Sample Output:
00000 4 33218 33218 3 12309 12309 2 00100 00100 1 99999 99999 5 68237 68237 6 -1
思路
用 STL 模拟 链表
然后 要注意 可能会有 多余结点 不在链表上面
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 5; const int MOD = 1e9 + 7; struct Node { int add; int value; int next; void read() { scanf("%d%d%d", &add, &value, &next); } }q[maxn]; vector <Node> v, ans; map <int, Node> m; void dfs(int add) { v.pb(m[add]); if (m[add].next != -1) dfs(m[add].next); } int main() { int start, n, k; scanf("%d%d%d", &start, &n, &k); for (int i = 0; i < n; i++) { q[i].read(); m[q[i].add] = q[i]; } dfs(start); n = v.size(); int len = v.size() / k; for (int i = 1; i <= len; i++) { int j = i * k - 1; int m = k; while (m--) ans.pb(v[j--]); } for (int i = len * k; i < n; i++) ans.pb(v[i]); for (int i = 0; i < n - 1; i++) printf("d %d d\n", ans[i].add, ans[i].value, ans[i + 1].add); printf("d %d -1\n", ans[n - 1].add, ans[n - 1].value); }转载于:https://www.cnblogs.com/Dup4/p/9433173.html
相关资源：JAVA上百实例源码以及开源项目