关于算法-数据结构:PAT甲级1133-Splitting-A-Linked-List

题目粗心：

给定一个单链表，节点数目 N 和阈值 K，从新将链表依照如下规定进行排序，节点值小于 0 的在最右边，[0,K]的在两头，大于 K 的在最左边, 同时同一类别的节点其绝对程序不能扭转.

算法思路:

算法思路 1:

因为题目给出的是动态链表, 那么数据和地址实际上是绑定在一起的,next 指针根本能够先不思考，咱们给链表上每一个节点设置一个 flag 和 id，别离示意以后节点的类别 (0 对应小于 0 的节点，1 对应[0,K] 的节点，2 对应大于 K 的节点), 节点在链表中的地位(用来记录绝对地位)，那么应用 nodes 数组承受所有的输出节点，而后将不在链表中的节点过滤后增加到 list 中，而后对 list 的节点进行排序，排序规定如下：flag 小的在前，flag 雷同的，id 小的在前。而后间接输入 list 数组即可，只须要留神以后节点不是最初一个节点的话，以后节点的 next 就是就是下一个节点的地址。

算法思路:

开拓第二个链表，第一遍遍历将所有的正数节点增加进新链表，第二次遍历将所有在 [0,K] 范畴的节点增加进新链表，第三次遍历将残余所有的节点增加进新链表。

留神点：

• 1、须要过滤输出的数据，防止出现有效节点(PAT 动态链表的套路)。

提交后果：

AC 代码 1：

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct Node{
    int address;
    int data;
    int next;
    int flag;
    int id;
}nodes[100005];
vector<Node> list;// 链表

bool cmp(const Node &a,const Node &b){return a.flag!=b.flag?a.flag<b.flag:a.id<b.id;}

int main(){
    int begin_address,N,K;
    scanf("%d %d %d",&begin_address,&N,&K);
    int address,data,next;
    for (int i = 0; i < N; ++i) {scanf("%d %d %d",&address,&data,&next);
        nodes[address].address = address;
        nodes[address].data = data;
        nodes[address].next = next;
        if(data<0){nodes[address].flag = 0;
        } else if(data<=K){nodes[address].flag = 1;
        } else {nodes[address].flag = 2;
        }
    }
    // 遍历所有节点，过滤有效节点
    int num = 1;
    while (begin_address!=-1){nodes[begin_address].id = num++;// 记录绝对地位
        list.push_back(nodes[begin_address]);
        begin_address = nodes[begin_address].next;
    }
    sort(list.begin(),list.end(),cmp);
    for (int j = 0; j < list.size(); ++j) {printf("%05d %d",list[j].address,list[j].data);
        if(j==list.size()-1){printf("-1");
        } else {printf("%05d\n",list[j+1].address);
        }
    }
    return 0;
}

AC 代码 2:

#include<cstdio>
#include<cstring>

using namespace std;

struct Node{
    int address;
    int data;
    int next;
}node1[100005];

int main(){
    int start,n,k;
    scanf("%d %d %d",&start,&n,&k);
    Node nodes[n];
    for(int i=0;i<n;++i){
        Node nd;
        scanf("%d %d %d",&nd.address,&nd.data,&nd.next);
        node1[nd.address] = nd;
    }
     int cnt = 0;
    // 第一次找出 data 为正数的
    Node root = node1[start];
    while (root.next!=-1){if (root.data<0){nodes[cnt++] = root;
        }
        root = node1[root.next];
    }
    if (root.data<0){nodes[cnt++] = root;
    }
    // 第二次遍历,[0,K]范畴的所有节点
    root = node1[start];
    while (root.next!=-1){if (root.data>=0&&root.data<=k){nodes[cnt++] = root;
        }
        root = node1[root.next];
    }
    if (root.data>=0&&root.data<=k){nodes[cnt++] = root;
    }
    // 第三次遍历，大于 K 的所有节点
    root = node1[start];
    while (root.next!=-1){if (root.data>k){nodes[cnt++] = root;
        }
        root = node1[root.next];
    }
    if (root.data>k){nodes[cnt++] = root;
    }
    // 更新 next 
    for (int i=0;i<cnt-1;++i){nodes[i].next = nodes[i+1].address;
    }
    nodes[cnt-1].next = -1;
    for (int i=0;i<cnt;++i){printf("%05d %d",nodes[i].address,nodes[i].data);
        if (nodes[i].next!=-1){printf("%05d\n",nodes[i].next);
        }else {printf("-1\n");
        }
    }
    return 0;
}