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