PAT(Advanced Level)A1133. Splitting A Linked List

题意

要让链表里的所有负数的结点排在非负数的前面，以及让所有的[0, K]的数字放在(k, ∞)的前面，而且要保持相对顺序不变。保证链表不为空

思路

• 依次遍历链表的每个结点进行标记，第一趟取出负数，第二趟取出[0, K]内的数字，第三趟取出剩下没有取的数字，标记的方式是令data = 100010，已知data的值域在[-10^5, 10^5]

代码

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <cmath>
using namespace std;
struct node {
    int address;
    int data;
    int next;
}linked_list[100100];
int main() {
    int st, N, K;
    scanf("%d %d %d", &st, &N, &K);
    int ads, val, next;
    for(int i = 0; i < N; i++) {
        scanf("%d %d %d", &ads, &val, &next);
        linked_list[ads] = {ads, val, next};
    }
    // 存放最后结果
    vector<node> ans;
    
    // 找<0的数字
    int cur = st;
    while(cur != -1) {
        if(linked_list[cur].data < 0) {
            ans.emplace_back(node{linked_list[cur].address, linked_list[cur].data, linked_list[cur].next});
        }
        cur = linked_list[cur].next;
    }
    
    // 找[0, K]的数字
    cur = st;
    while(cur != -1) {
        if(linked_list[cur].data >= 0 && linked_list[cur].data <= K) {
            ans.emplace_back(node{linked_list[cur].address, linked_list[cur].data, linked_list[cur].next});
        }
        cur = linked_list[cur].next;
    }
    
    // 找剩下的数字
    cur = st;
    while(cur != -1) {
        if(linked_list[cur].data > K)
        ans.emplace_back(node{linked_list[cur].address, linked_list[cur].data, linked_list[cur].next});
        cur = linked_list[cur].next;
    }
    for(int i = 0; i < ans.size() - 1; i++) {
        printf("%05d %d %05d
", ans[i].address, ans[i].data, ans[i + 1].address);
    }
    printf("%05d %d %d", ans.back().address, ans.back().data, -1);
    return 0;
}

P