数据结构_1074 Reversing Linked List （25 分）

1074 Reversing Linked List （25 分）

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 Lbeing 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.

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

给出链表的头部，长度以及翻转的长度单位，然后给出整个链表（链表上一个节点，当前节点数据，下一个节点），-1表示链表结尾，我们需要将链表根据单位长度进行翻转，最后不满足单位长度的直接原序输出

找出原序列，直接使用algorithm头文件中的reverse函数直接对容器进行翻转即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>
#define INF 0x3f3f3f3f

using namespace std;
const int maxn = 1e5+5;
map<int,int> m;
struct Node
{
    int head,data,_next;
}node[maxn];


int main()
{
    int head,len,k;
    scanf("%d%d%d",&head,&len,&k);
    for(int i = 0;i < len;i ++)
    {
        scanf("%d%d%d",&node[i].head,&node[i].data,&node[i]._next);
        m[node[i].head] = i;      //表示头结点存储在结构体中的位置
    }
    int pos = head;
    vector<Node> vec;
    while(true)
    {
        if(vec.size() % k == 0 && vec.size() != 0)
            reverse(vec.end()-k,vec.end());

        if(pos == -1)
            break;
        else
            pos = m[pos];
        vec.push_back(node[pos]);
        pos = node[pos]._next;
    }
    for(int i =0 ;i < vec.size();i ++)
    {
        printf("%05d %d ",vec[i].head,vec[i].data);
        if(i == vec.size()-1)
            printf("-1\n");
        else
            printf("%05d\n",vec[i+1].head);
    }
    return 0;
}