1074 Reversing Linked List （25 分)

2019-04-04

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 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:

1	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

作者: CHEN, Yue

单位: 浙江大学

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

给出一个链表，给出k，要求以k为一组翻转链表

分析

使用map<int,node>记录地址和结点，利用vector<node>暂存结点。从头结点开始，读取k个结点进vector，将其翻转。判断剩余结点是否大于k个。如果大于k个，则vec[0]结点的next为向后数k个结点的地址。如果小于则不翻转，对应的next为vec[k-1]的next。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include <sstream>

using namespace std;
struct  node{
    int addr;
    int data;
    int next;
    node(int addr, int data, int next) : addr(addr), data(data), next(next) {}
    node() {}
};
map<int,node> list,rev;

int main() {
    int addr,data,next;
    int head,n,k;
    cin>>head>>n>>k;
    if(head==-1){
        cout<<"00000 0 -1";
        return 0;
    }
    for(int i=0;i<n;i++){
        cin>>addr>>data>>next;
        node n(addr,data,next);
        list[addr]=n;
    }
    vector<node> vec;
    int temp=head,f=0;
    while(temp!=-1){
        vec.push_back(list[temp]);
        if(vec.size()==k){
            if(f==0){
                f=1;
                head=vec[k-1].addr;
            }
            for(int i=k-1;i>0;i--){
                vec[i].next=vec[i-1].addr;
                rev[vec[i].addr]=vec[i];
            }
            int ttemp=temp,c=0;
            while(list[ttemp].next!=-1&&c<k){
                ttemp=list[ttemp].next;
                c++;
            }
            if(c==k)
                vec[0].next=ttemp;
            else
                vec[0].next=list[temp].next;
            rev[vec[0].addr]=vec[0];
            vec.clear();
        }
        temp=list[temp].next;
    }
    if(!vec.empty())
        for(auto n:vec)
            rev[n.addr]=n;
    temp=head;
    while(rev[temp].next!=-1){
        printf("%05d %d %05d\n",temp,rev[temp].data,rev[temp].next);
        temp=rev[temp].next;
    }
    printf("%05d %d -1\n",temp,rev[temp].data);
    return 0;
}

其他

注意测试点5的情况，对应 L%k=(k-1)的情况。例如7个结点，k=4。