博客

L2-002 链表去重

给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。

输入格式：



输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤10^​5​​ ，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。随后 N 行，每行按以下格式描述一个结点：



地址 键值 下一个结点



其中地址是该结点的地址，键值是绝对值不超过10^​4的整数，下一个结点是下个结点的地址。

输出格式：



首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。

输入样例：

00100 5
99999 -7 87654
23854 -15 000000
87654 15 -1
00000 -15 99999
00100 21 23854

输出样例：

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

代码长度限制																	16 KB
时间限制																		400 ms
内存限制																		64 MB

借鉴网上的：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>

using namespace std;

struct Node
{
    int address;
    int data;
    int nextAddress;
};

int main()
{
    Node link[100010];//让数组元素下标作为链表的地址
    memset(link, 0, sizeof(link));

    int FirstAddress,num;
    scanf("%d %d",&FirstAddress,&num);

    for(int i=0;i<num;i++)//录入数据
    {
        int address,data,nextAddress;
        scanf("%d %d %d",&address,&data,&nextAddress);
        link[address].address=address;
        link[address].data=data;
        link[address].nextAddress=nextAddress;
    }

    int link1[100010],link2[100010];//申请两个数组顺序存储地址
    int arrValue[100010];//申请一个数组,用数组下标记录值
    memset(link1, 0, sizeof(link1));
    memset(link2, 0, sizeof(link2));
    int len_link1=0,len_link2=0;

    //遍历链表,并进行拆分
    for(int i=FirstAddress;i!=-1;i=link[i].nextAddress)
    {
        int temp=link[i].data;
        if(temp<0)
            temp=-temp;
        if(arrValue[temp]==0)//首次出现，放入link1中
        {
            arrValue[temp]++;
            link1[len_link1]=i;
            len_link1++;
        }
        else//元素重复出现,放到link2中 
        {
            link2[len_link2]=i;
            len_link2++;
        }
    }

    //输出两个链表
    for(int i=0;i<len_link1;i++)
    {
        if(i==len_link1-1)
            printf("%05d %d -1\n",link1[i],link[link1[i]].data);
        else
            printf("%05d %d %05d\n",link1[i],link[link1[i]].data,link1[i+1]);
    }
    for(int i=0;i<len_link2;i++)
    {
        if(i==len_link2-1)
            printf("%05d %d -1\n",link2[i],link[link1[2]].data);
        else
            printf("%05d %d %05d\n",link2[i],link[link2[i]].data,link2[i+1]);
    }

    return 0;
}

自己原来写的笨方法：

#include <cstdio>
#include <stdio.h>
#include <cstring>
#include <string.h>
#include <cmath>
#include <iostream>

using namespace std;

struct Node
{
    int address;
    int data;
    int nextAddress;
};

const int MAXN=100;
int arr[MAXN];

int main()
{
    int startAddress,num;
    scanf("%d %d",&startAddress,&num);
    Node nodes[num];
    for(int i=0;i<num;i++)
        scanf("%d %d %d",
            &nodes[i].address,&nodes[i].data,&nodes[i].nextAddress);
    Node newNodes[num];
    for(int i=0;i<num;i++)
    {
        if(nodes[i].address==startAddress)
        {
            newNodes[0]=nodes[i];
            break;
        }
    }
    int count=0;
    //将结点按地址顺序连接起来
    for(int i=0;i<num;i++)
    {
        for(int j=0;j<num;j++)
        {
            if(newNodes[count].nextAddress==nodes[j].address)
            {
                newNodes[count+1]=nodes[j];
                count++;
            }
        }
        if(count==num-1)
            break;
    }

    // printf("\n\n\n");
    // for(int i=0;i<num;i++)
    // {
    //     printf("%05d %d",
    //         newNodes[i].address,newNodes[i].data);
    //     if(newNodes[i].nextAddress<0)
    //         printf(" %d\n",newNodes[i].nextAddress);
    //     else
    //         printf(" %05d\n",newNodes[i].nextAddress);
    // }

    int count1=num,count2=0;//记录去重后的链表和去掉的结点个数
    Node quchong[count1];
    Node chong[num];
    for(int i=0;i<count1;i++)//复制一份出来
        quchong[i]=newNodes[i];
        
    for(int i=0;i<MAXN;i++)
        arr[i]=0;   //初始化

    for(int i=0;i<num;i++)  //记录重复数出现的次数
        arr[abs(newNodes[i].data)]++;
    
    //得到去重掉的数
    for(int i=0;i<MAXN;i++)
    {
        if(arr[i]>1)//有重根
        {
            int flag=0;
            for(int j=0;j<num;j++)
            {
                if(abs(quchong[j].data)==i)
                {
                    flag++;
                    if(flag>1)  //有重根
                    {
                        chong[count2]=quchong[j];
                        count2++;
                    }
                }
            }
        }
    }

    //得到去重后的数组
    for(int i=0;i<count1;i++)
    {
        for(int j=i+1;j<count1;j++)
        {
            if(abs(quchong[i].data)==abs(quchong[j].data))
            {
                for(int k=j;k<num;k++)
                    quchong[k]=quchong[k+1];
                count1--;
                j--;
            }
        }
    }

    //地址进行相连
    for(int i=0;i<count1-1;i++)
        quchong[i].nextAddress=quchong[i+1].address;
    quchong[count1-1].nextAddress=-1;

    //地址进行相连
    for(int i=0;i<count2-1;i++)
        chong[i].nextAddress=chong[i+1].address;
    chong[count2-1].nextAddress=-1;

    for(int i=0;i<count1;i++)
    {
        printf("%05d %d",
            quchong[i].address,quchong[i].data);
        if(quchong[i].nextAddress<0)
            printf(" %d\n",quchong[i].nextAddress);
        else
            printf(" %05d\n",quchong[i].nextAddress);
    }
    for(int i=0;i<count2;i++)
    {
        printf("%05d %d",
            chong[i].address,chong[i].data);
        if(chong[i].nextAddress<0)
            printf(" %d\n",chong[i].nextAddress);
        else
            printf(" %05d\n",chong[i].nextAddress);
    }
    return 0;
}