題目

給定一個(gè)單鏈表，請(qǐng)編寫程序?qū)㈡湵碓剡M(jìn)行分類排列，使得所有負(fù)值元素都排在非負(fù)值元素的前面，而 [0, K] 區(qū)間內(nèi)的元素都排在大于 K 的元素前面。但每一類內(nèi)部元素的順序是不能改變的。例如：給定鏈表為 18→7→-4→0→5→-6→10→11→-2，K 為 10，則輸出應(yīng)該為 -4→-6→-2→7→0→5→10→18→11。

輸入格式：

每個(gè)輸入包含一個(gè)測(cè)試用例。每個(gè)測(cè)試用例第 1 行給出：第 1 個(gè)結(jié)點(diǎn)的地址；結(jié)點(diǎn)總個(gè)數(shù)，即正整數(shù)N (≤10?5??)；以及正整數(shù)K (≤10?3??)。結(jié)點(diǎn)的地址是 5 位非負(fù)整數(shù)，NULL 地址用 ?1 表示。

接下來(lái)有 N 行，每行格式為：

Address Data Next

其中 Address 是結(jié)點(diǎn)地址；Data 是該結(jié)點(diǎn)保存的數(shù)據(jù)，為 [?10?5??,10?5??] 區(qū)間內(nèi)的整數(shù)；Next 是下一結(jié)點(diǎn)的地址。題目保證給出的鏈表不為空。

輸出格式：

對(duì)每個(gè)測(cè)試用例，按鏈表從頭到尾的順序輸出重排后的結(jié)果鏈表，其上每個(gè)結(jié)點(diǎn)占一行，格式與輸入相同。

輸入樣例：

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

輸出樣例：

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

通過(guò)代碼

#include <iostream>

using namespace std;

struct node {
    int add;
    int next;
    int data;
};

int first, num, k;
node v[100005];
node x[100005];
node a[100005], b[100005], c[100005];
void print(node* m, int size) {
    for (int i = 0; i < size - 1; i++)
        printf ("%05d %d %05d\n", m[i].add, m[i].data, m[i + 1].add);
    printf ("%05d %d -1\n", m[size - 1].add, m[size - 1].data);
}

int get() {
    scanf ("%d%d%d", &first, &num, &k);
    node temp;
    for (int i = 0; i < num; i++) {
        scanf ("%d%d%d", &temp.add, &temp.data, &temp.next);
        v[temp.add] = temp;
    }
    int find = first;
    int c = 0;
    while (find != -1) {
        x[c++] = (v[find]);
        find = v[find].next;
    }
    return c;
}

int main () {
    int real = get();
    int an = 0, bn = 0, cn = 0;
    for (int i = 0; i < real; i++) {
        if (x[i].data < 0)  a[an++] = (x[i]);
        else if (x[i].data > k)  c[cn++] = (x[i]);
        else  b[bn++] = (x[i]);
    }
    int count = 0;
    for (int i = 0; i < an; i++) x[count++] = a[i];
    for (int i = 0; i < bn; i++) x[count++] = b[i];
    for (int i = 0; i < cn; i++) x[count++] = c[i];
    print(x, real);
    return 0;
}

思路與注意

1. 輸入數(shù)據(jù)（由于后面要還原鏈表，為了降低復(fù)雜度，把a(bǔ)ddr當(dāng)做引索）

2. 把鏈表先還原，同時(shí)返回還原后的節(jié)點(diǎn)個(gè)數(shù)（因?yàn)橛锌赡苣承┕?jié)點(diǎn)不在鏈表上）

3. 分類統(tǒng)計(jì)，最后再重新排回去

4. 輸出（輸出的時(shí)候最好把它變成一個(gè)整體，不要分塊輸出（可能存在某一部分空的情況））

反思與評(píng)價(jià)

• 這道題就是改了改反轉(zhuǎn)鏈表

• 思想實(shí)際上是德才論和反轉(zhuǎn)鏈表的綜合，簡(jiǎn)單題

• 反轉(zhuǎn)鏈表用vector可以過(guò)，但是這個(gè)題用vector就會(huì)段錯(cuò)誤，所以用普通數(shù)組