Note / Problem
  6 minutes read (About 967 words)

PAT-A 1133 Splitting A Linked List (25)

  又是链表，又是段错误。

Given a singly linked list, you are supposed to rearrange its elements so that all the negative values appear before all of the non-negatives, and all the values in [0, K] appear before all those greater than K. The order of the elements inside each class must not be changed. For example, given the list being 18 → 7 → -4 → 0 → 5 → -6 → 10 → 11 → -2 and K being 10, you must output -4 → -6 → -2 → 7 → 0 → 5 → 10 → 18 → 11.

Problem: PAT-A 1133 Splitting A Linked List

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 (≤ $10^3$ ). 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 in [−$10^5$, $10^5$], and Next is the position of the next node. It is guaranteed that the list is not empty.

Output Specification

For each case, output in order (from beginning to the end of the list) the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input

1
2
3
4
5
6
7
8
9
10
00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218

Sample Output

1
2
3
4
5
6
7
8
9
33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

Analysis

  题目大意：给一个链表，和一个正整数 K，要求链表中值为负数的元素在最左边，小于 K 的元素在 K 左边，大于 K 的元素在 K 右边。输出修改后的链表内容。

  遍历链表，将小于 0 的元素、大于等于 0 且小于等于 K 的元素、大于 K 的元素分别保存于 3 个不同的数组中，使用 push_back() 确保顺序。不需要修改结点的 Next 属性，在输出 Next 时直接输出数组中下一结点的地址。

  数字 K 不一定存在于链表中；根据思路划分的三个数组均可能为空，注意数组越界。

Code

  下面是第一回过的代码，比较莽，输出占了大部分。分了三个数组，整了一堆判断，起初在这段代码上被数组越界玩死了。

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
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int addr, data, nxt;
};

map<int, Node> mp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int hd, N, K;
    cin >> hd >> N >> K;
    for (int i = 0; i < N; i++) {
        Node tmp;
        cin >> tmp.addr >> tmp.data >> tmp.nxt;
        mp[tmp.addr] = tmp;
    }

    vector<Node> neg, kl, kr;
    while (hd != -1) {
        if (mp[hd].data < 0) {
            neg.push_back(mp[hd]);
        } else if (mp[hd].data <= K) {
            kl.push_back(mp[hd]);
        } else {
            kr.push_back(mp[hd]);
        }
        hd = mp[hd].nxt;
    }

    int len = neg.size();
    for (int i = 0; i < len; i++) {
        printf("%05d %d ", neg[i].addr, neg[i].data);
        if (i == len - 1) {
            if (!kl.empty()) {
                printf("%05d\n", kl[0].addr);
            } else if (!kr.empty()){
                printf("%05d\n", kr[0].addr);
            } else {
                printf("-1\n");
            }
        } else {
            printf("%05d\n", neg[i + 1].addr);
        }
    }
    len = kl.size();
    for (int i = 0; i < len; i++) {
        printf("%05d %d ", kl[i].addr, kl[i].data);
        if (i == len - 1) {
            if (!kr.empty()) {
                printf("%05d\n", kr[0].addr);
            } else {
                printf("-1\n");
            }
        } else {
            printf("%05d\n", kl[i + 1].addr);
        }
    }
    len = kr.size();
    for (int i = 0; i < len; i++) {
        printf("%05d %d ", kr[i].addr, kr[i].data);
        if (i == len - 1) {
            printf("-1\n");
        } else {
            printf("%05d\n", kr[i + 1].addr);
        }
    }
}

  下面是简化后的代码，可读性较强。

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
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int addr, data, nxt;
};

map<int, Node> mp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int hd, N, K;
    cin >> hd >> N >> K;
    for (int i = 0; i < N; i++) {
        Node tmp;
        cin >> tmp.addr >> tmp.data >> tmp.nxt;
        mp[tmp.addr] = tmp;
    }

    vector<Node> v[3];
    while (hd != -1) {
        if (mp[hd].data < 0) {
            v[0].push_back(mp[hd]);
        } else if (mp[hd].data <= K) {
            v[1].push_back(mp[hd]);
        } else {
            v[2].push_back(mp[hd]);
        }
        hd = mp[hd].nxt;
    }

    int flag = 0;
    for (int i = 0; i < 3; i++) {
        int len = v[i].size();
        for (int j = 0; j < len; j++) {
            if (!flag++) {
                printf("%05d %d ", v[i][j].addr, v[i][j].data);
            } else {
                printf("%05d\n%05d %d ", v[i][j].addr, v[i][j].addr, v[i][j].data);
            }
        }
    }
    printf("-1\n");
}

Tsukkomi

  开始没仔细读题，以为 K 是链表中的元素，于是在第一遍的代码中默认第二个数组一定不为空了。交上去发现有两个测试点提示段错误，还有点怀疑人生。代码也写得太乱了，其实难度不大，但浪费了不少时间。


# , 

Like this article? Support the author with

PAT-A 1030 Travel Plan (30)
PAT-A 1127 ZigZagging on a Tree (30)
  Github
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×