关于算法-数据结构: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;
}