1.题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805369774129152
去除链表上权值的绝对值相同的结点（只保留一个），再输出链表现存的结点，最后也要输出被删除的结点（按在原链表中的顺序输出）。
2.思路
首先要明确有三类结点：未删除的结点、已删除的结点、无效结点。
（1）定义静态链表。
——order变量表示结点在链表上的序号，最后需要先输出所有未删除的结点，然后输出所有被删除的结点，因此可在后面令未删除的结点的order从0开始编号，被删除的结点的order从maxn开始编号。
（2）初始化。令order的初值均为2 maxn——区分无效结点。
（3）设置countValid（初始化为0），记录未删除的有效结点的个数；
设置countRemoved（初始化为0），记录被删除的有效结点的个数。
【现在从头到尾遍历链表】
若当前访问结点的权值的绝对值还未出现过（用bool数组isExist[]记录），就把该结点的order设为countVaild，且加一；
若出现过则把该结点的order设为maxn+countRemoved，且加一。
——实现未删除的结点的order从0开始编号，被删除的结点从maxn开始编号。
PS：这里判断的“出现”——if(!isExist[abs(node[p].data)])。
（4）对结点排序，cmp——按order从小到大排序。
（5）输出链表。记count为countValid与countRemoved之和，之后将node[0]~node[count-1]输出。注意最后一个未删除结点和最后一个被删除结点要单独处理。
3.代码
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> #include<algorithm> #include<map> #include<vector> #include<queue> using namespace std; //key:注意两个链表输出时分别以-1结尾!! const int maxn=100005; const int TABLE=1000010; struct Node{ //定义静态链表(步骤1) int address,data,next; int order; //结点在链表上的序号，无效结点记为2 maxn }node[maxn]; bool isExist[TABLE]={false}; //绝对值是否已经出现 bool cmp(Node a,Node b){ return a.order<b.order; } int main(){ memset(isExist,false,sizeof(isExist)); //初始化isExist为未出现 for(int i=0;i<maxn;i++){ //初始化(步骤2) node[i].order=2*maxn; //表示初始时均为无效结点 } int n,begin,address; scanf("%d%d",&begin,&n); //起始地址，结点个数 for(int i=0;i<n;i++){ //输入所有结点 scanf("%d",&address); scanf("%d%d",&node[address].data,&node[address].next); node[address].address=address; } //未删除的有效结点个数和已删除的有效结点个数 int countValid=0,countRemoved=0,p=begin; while(p != -1){ //枚举链表(步骤3) if(!isExist[abs(node[p].data)]){ //data的绝对值不存在 isExist[abs(node[p].data)] = true; //标记为已存在 node[p].order=countValid++; //不删除，编号从0开始 }else{ //data的绝对值已存在 node[p].order=maxn+countRemoved++; //被删除，编号从maxn开始 } p=node[p].next; //下一个结点 } sort(node,node+maxn,cmp); //按照order从小到大排序(步骤4) //输出结果(步骤5) int count=countValid+countRemoved; //有效结点个数 for(int i=0;i<count;i++){//!!!!!!!最巧妙就是介个for里，实现两个链表-1结束 if(i != countValid-1 && i !=count-1){ //非最后一个结点 printf("%05d %d %05d\n",node[i].address,node[i].data,node[i+1].address); }else{ //最后一个结点单独处理 printf("%05d %d -1\n",node[i].address,node[i].data); } } system("pause"); return 0; }
4.注意
（1）说到底，这种静态链表的题最终还是没对next改变；
（2）连标题大致套路就是：定义结构体、初始化、输入、枚举链表同时改变某个结构体标记，以方便后面排序、输出。而且注意标记是根据具体题目确定的，如这题就是结构体里的order变量改变结点的优先级，而初始化时是将所有结点的order初始化为无效结点，即node[i].order=2*max。
（3）根据题目要求，最后是有两个结点的next是-1的，所以最后输出的for循环内不要漏了if(i!=countValid-1&&i!count-1)的countValid。
