首页 > itarticle > pat

pat

admin 11月 14, 2020 0

题目

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 (≤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

思路

一开始直接当作链表来处理，逻辑相当复杂，指针飞来飞去的简直要崩溃，勉强AC了。看了一下别人的答案，原来直接用一个数组来模拟链表就好，牺牲了空间复杂度，但是代码非常的简单易懂。

##代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 

//#include <iomanip>
//using namespace std;
//int Data[100000+10];
//int Next[100000+10];
//int Add[100000+10];
//int main()
//{
//    int head,N,K;
//    cin >> head >> N >> K;
//    int add;
//    for(int i=0;i<N;i++){
//        cin >> add;
//        cin >> Data[add] >> Next[add];
//    }
//    Next[100000+5] = head;
//    if(K>1){
//        int now = 100000+5;
//        while(true){
////            cout << "now: " <<now << endl;
//            int k=0;
//            while(k<=K+1){
//                Add[k] = now;
////                cout << "Add: " << k << " " << Add[k] << endl;
//                k++;
//                if(now==-1) break;
//                now = Next[now];
//            }
//            if(k==K+2){
//                Next[Add[0]] = Add[K];
//                Next[Add[1]] = Add[K+1];
//                for(int i=2;i<=K;i++){
//                    Next[Add[i]] = Add[i-1];
//                }
//            }else break;
//            now = Add[1];
//        }
//
//    }
//    int now = Next[100000+5];
//    while(now!=-1){
//        cout.width(5);cout.fill('0');
//        cout << now << " " << Data[now] << " ";
//        now = Next[now];
//        if(now!=-1){ cout.width(5);cout.fill('0');}
//        cout << now << "n";
//    }
//
//    return 0;
//}



#include <algorithm>
using namespace std;
int Data[100000+10];
int Next[100000+10];
int Add[100000+10];
int (){
    int head,N,K;
    cin >> head >> N >> K;
    int address;
    for(int i=0;i<N;i++){
        cin >>address;
        cin >> Data[address] >> Next[address];
    }
    int num = 0;
    while(head!=-1){
        Add[num++] = head;
        head = Next[head];
    }
    for(int i=0;i<num/K;i++){
        reverse(Add+K*i,Add+K*i+K);
    }
    for(int i=0;i<num-1;i++){
        printf("%05d %d %05dn",Add[i],Data[Add[i]],Add[i+1]);
//        cout << Add[i] << " " << Data[Add[i]] << " " << Add[i+1]<< "n";
    }
    printf("%05d %d %dn",Add[num-1],Data[Add[num-1]],-1);
    return 0;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能