题目粗心：
给定一个单链表，节点数目 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;
}