PAT乙级1075 || 链表元素分类（详解，C/C++示例，测试点分析）

Posted on In

链表元素分类

题目描述

给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而 [0, K] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K 为 10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。

输入格式

每个输入包含一个测试用例。每个测试用例第 1 行给出：第 1 个结点的地址；结点总个数，即正整数N (≤$10^5$)；以及正整数K (≤$10^3$)。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。

接下来有 N 行，每行格式为：

1
Address Data Next

其中 Address 是结点地址；Data 是该结点保存的数据，为 [−$10^5$, $10^5$] 区间内的整数；Next 是下一结点的地址。题目保证给出的链表不为空。

输出格式

对每个测试用例，按链表从头到尾的顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例

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

输出样例

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

问题解决

解题思想

又是一道费时的题，这种乙级难度的题竟然还能如此费劲，一定是我太弱了@^@。

这种题其实有更简单的方法，三个数组分别放三类数分别输出就行了，可是我就是想试试链表的拆接。链表的拆接有太多的小细节要处理了，多次把自己搞入了绝境。最后还是靠自己一个测试点一个测试点的解决，逐渐完善特殊情况的处理，最终才全部通过。

链表拆接的思想其实很简单，概括起来就是：遇到负值就接到前面负值区域最后一个的后面，遇到[0,k]区间内的值就接到前面[0, k]区域的最后一个的后面，注意拆下来的时候要注意防止断链，接上去的时候要注意前后接完整。

小细节太多了，具体看下面的代码吧。

坑点提醒

测试点1

原链表顺序中有连续的负值，这个需要特殊处理。

测试点4

需要注意的是输入的数据中可能存在不在链表中的废数据，比如测试点4，所以在遍历筛选和输出时不能用输入节点个数为准，应以结束地址-1和有效链表长度为准。比如下面的测试用例中就含有废数据：

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

测试点5

原链表顺序中有连续的处于区域[0, k]之间的数，这个需要特殊处理。

代码示例（C/C++）

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <cstdio>
using namespace std;

struct node {
    int data, next;
}node[100000];

int main() {
    int addr_first, num, k;
    scanf("%d%d%d", &addr_first, &num, &k);
    for(int i = 0; i < num; i++) {
        int addr1, addr2, tmp;
        scanf("%d%d%d", &addr1, &tmp, &addr2);
        node[addr1].data = tmp;
        node[addr1].next = addr2;
    }
    int first1, end1, first2, end2;  //first1，end1负值结点的第一个元素和最后一个元素的地址，first2，end2处于[0, k]之间的第一个元素的和最后一个元素的地址
    first2 = addr_first;
    int flag1 = 1, flag2 = 1;   //分别标记负值元素和处于[0,k]之间的元素的第一个插入
    for(int p = addr_first, pre = addr_first; p != -1; ) {   //p为遍历指针，pre为遍历指针的上一个元素地址
        if(node[p].data < 0){
            if(flag1) {
                node[pre].next = node[p].next;  //摘下来
                addr_first = first1 = end1 = p;
                if(p != pre) {
                    node[p].next = first2;
                }
                else {  //第一个元素为负值
                    first2 = node[p].next;
                }
                flag1 = 0;
            }
            else {
                if(node[pre].data < 0) {    //特殊处理连续的负值
                    end1 = pre = p;
                    p = node[p].next;
                    first2 = p;
                    continue;
                }
                else {
                    node[pre].next = node[p].next;  //摘下来
                }
                node[end1].next = p;
                node[p].next = first2;
                end1 = p;   //note
            }
            p = node[pre].next;
        }
        else if(node[p].data >= 0 && node[p].data <= k) {
            if(node[pre].data >=0 && node[pre].data <= k) { //特殊处理连续的处于[0,k]之间的数
                end2 = pre = p;
                p = node[p].next;
                if(flag2) {
                    flag2 = 0;
                }
                continue;
            }
            else {
                node[pre].next = node[p].next;  //摘下来
            }
            if(flag2) {
                if(p != pre) {
                    if(first2 != p) {
                        node[p].next = first2;
                    }
                    else {
                        pre = p;
                    }
                }
                 first2 = end2 = p;
                if(flag1) { //负值结点还未插入
                    addr_first = first2;
                }
                else {
                    node[end1].next = first2;   //note
                }
                flag2 = 0;
            }
            else {
                node[p].next = node[end2].next;
                node[end2].next = p;
                end2 = p;   //note
            }
            p = node[pre].next;
        }
        else {
            pre = p;
            p = node[p].next;
        }
    }
    for(int p = addr_first; p != -1; p = node[p].next) {
        printf("%05d %d ", p, node[p].data);
        if(node[p].next == -1) {
            printf("%d\n", node[p].next);
        }
        else {
            printf("%05d\n", node[p].next);
        }
    }
    return 0;
}

题目来源：PAT乙级1075
作者：CHEN, Yue
单位：浙江大学

稀罕作者