L2_002链表去重（未解决）

• 啊难受我今天晚上就写了这么一道题还只通过了两个测试点，其他就答案错误和运行超时，但我又找不出代码哪错了，而且我也不觉得哪里会使他超时，循环只在读数据，处理数据，输出数据的时候各执行了一次，难道是有数据让程序陷入死循环了吗？
  emmm我的思路就是普通的链表，先读进去，然后先处理第一个结点，再让pos指向（下标）上一个结点，tp指向要处理的结点，若tp结点的key已存在，则删除tp这个结点，pos的next变成tp的next，pos不变，tp变为原tp的下一个结点（即pos的下一个结点）。若被删除链表此时还是空的（用一个flag来指示），那就把tp付给delete_head（表示被删除链表的头）和delete_last（被删除链表的尾），若非空则把tp付给delete_last的next，并更新delete_last。若tp的key还不存在则使该key存在，pos变成tp，tp变成pos的下一个结点。当tp为-1时退出循环，并将delete_last的next变为-1，然后再分别已head，delete_head位开头输出链表

• 超时的那两个测试点，我把cin，cout改成scanf，printf就通过了，竟然啊啊啊啊啊啊，好吧以后要注意了！！
  但第三个测试点错误还是没解决

• 啊越改越错了，错过回寝室时间了啊啊啊啊啊啊啊今天晚上三个小时啊，就这一道题还没解决，心态崩了啊啊啊啊啊权当给比赛攒运气好了T_T

这个人用的方法跟我一摸一样但他说他ac了
https://www.cnblogs.com/yinzm/p/5499231.html

#include <iostream>
#include <iomanip>
#include <cmath>
#define N 100000
using namespace std;
struct node{
    int key;
    int next;
};
node arr[N];
int have[10001]={0};
int main()
{
    int head,delete_head,delete_last;
    int n;
    cin>>head>>n;
    int flag=0;
    for(int i=1;i<=n;++i){
        int xadd,xkey,xnext;
        cin>>xadd>>xkey>>xnext;
        node no;
        no.key=xkey;no.next=xnext;
        arr[xadd]=no;
    }
    int a=abs(arr[head].key);
    have[a]=1;
    int pos=head;
    int tp=arr[pos].next;
    while(tp!=-1){
        //int tp=arr[pos].next;
        //注意审题是绝对值！！
        int a=abs(arr[tp].key);
        if(have[a]){
            if(!flag){
                delete_head=tp;
                delete_last=tp;
                flag=1;
            }else{
                arr[delete_last].next=tp;
                delete_last=tp;
            }
            arr[pos].next=arr[tp].next;
        }else{
            //这里也是绝对值之前忘改了
            have[a]=1;
            pos=tp;
        }
        tp=arr[pos].next;
        //pos=tp;//此处tp可能已经被删掉了不能这样写！！
        //pos=arr[pos].next;
        //tp=arr[tp].next;注意这部多余啦！！
    }
    arr[delete_last].next=-1;
    pos=head;
    int flag2=0;
    while(pos!=-1){
        if(flag2)
            cout<<endl;
        flag2=1;
        cout<<setw(5)<<setfill('0')<<pos<<" "<<arr[pos].key<<" ";
        if(arr[pos].next!=-1)
        {
            cout<<setw(5)<<setfill('0')<<arr[pos].next;
        }
        else
            cout<<-1;
        pos=arr[pos].next;
    }
    pos=delete_head;
    while(pos!=-1)
    {
        cout<<endl;
        cout<<setw(5)<<setfill('0')<<pos<<" "<<arr[pos].key<<" ";
        if(arr[pos].next!=-1)
        {
            cout<<setw(5)<<setfill('0')<<arr[pos].next;
        }
        else
            cout<<-1;
        pos=arr[pos].next;
    }
    return 0;
}

• 之前的问题倒是还没有解决
  然后参考了这位的代码
  https://www.liuchuo.net/archives/2125
• 思路：
  结构体中有address，key，next，num。num是等下用来排序的，将bum初始值为2maxn（数组最大长度）
  一开始放的时候要根据address把数据放到数组中，因为之后要遍历
  对于留下链表，删除链表，其中的元素的顺序都是与原链表中相同的
  所以元素的顺序就是遍历他们时遇到的顺序，并不用更改结点的next，只需利用num标记它们的先后顺序即可
  用cnt1，cnt2来标记留下链表，删除链表的元素个数
  当遇到key存在的点时，将其num赋为maxn+cnt2
  否则赋为cnt1
  然后利用num进行sort排序，由于不存在的点的num都是2maxn所以排完序后前cnt1是留下链表，cnt1后面cnt2个就是删除链表

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <math.h>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#define N 100000
#define K 10001
using namespace std;
struct node
{
    int addr;
    int key;
    int next;
    int num;
};
bool comp(node &n1, node &n2)
{
    return n1.num < n2.num;
}
node nums[N];
int have[K] = { 0 };
int main()
{
    int start, n;
    scanf("%d%d", &start, &n);
    for (int i = 0; i < N; ++i) {
        nums[i].num = 2 * N;
        //注意是全部都要初始化成2N而不只是读到的数据
    }
    for (int i = 0; i < n; ++i) {
        int taddr;
        scanf("%d", &taddr);
        nums[taddr].addr = taddr;
        scanf("%d", &nums[taddr].key);
        scanf("%d", &nums[taddr].next);
        //nums[taddr].num = 2 * N;
    }
    int cnt1 = 0, cnt2 = 0;
    int t = start;
    while (t != -1) {
        if (have[abs(nums[t].key)]) {
            nums[t].num = N + cnt2;
            ++cnt2;
        }
        else {
            have[abs(nums[t].key)] = 1;
            nums[t].num = cnt1;
            ++cnt1;
        }
        t = nums[t].next;
    }
    sort(nums, nums + N,comp);
    int cnt = cnt1 + cnt2;
    for (int i = 0; i < cnt; ++i)
    {
        if (i)
            cout << endl;
        printf("%05d %d ", nums[i].addr, nums[i].key);
        if (i == cnt - 1 || i == cnt1 - 1)
            cout << -1;
        else
            printf("%05d", nums[i+1].addr);
    }
    system("pause");
    return 0;
}