反轉(zhuǎn)子鏈表
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.
每隔固定長(zhǎng)度對(duì)鏈表進(jìn)行一次翻轉(zhuǎn)糠惫，最后按題目要求輸出
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.
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
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
struct data{
int val;
int next;
};
vector<data> v(100000);
vector<data> v_n2a;
int main(){
int n,m,start;
scanf("%d %d %d", &start,&n, &m);
int address, val, next;
int i, j, k;
for(i=0;i<n;i++){
scanf("%d %d %d",&address, &val, &next);
v[address].val = val;
v[address].next = next;
}
for(i=start;i!=-1;i=v[i].next){
//printf("%05d %d %05d\n",i,v[i].val,v[i].next);
v_n2a.push_back({v[i].val, i});
}
for(i=0;i+m-1<v_n2a.size();i+=m){
j = i+m-1;
k = i;
while(k<j){
//cout << i << " " <<v_n2a[i].val << endl;
swap(v_n2a[k],v_n2a[j]);
//cout << i << " " << v_n2a[i].val << endl;
k++,j--;
}
}
for(i=0;i<v_n2a.size();i++){
if(i!=v_n2a.size()-1){
printf("%05d %d %05d\n",v_n2a[i].next,v_n2a[i].val,v_n2a[i+1].next);
}else{
printf("%05d %d -1\n",v_n2a[i].next,v_n2a[i].val);
}
}
return 0;
}
