删除链表中相同的元素

前言：

链表是一种常见的数据结构，他是线性表的一种，他的典型特征就是数据结点之间通过指针相连，链表主要适合存储插入、删除操作比较频繁的数据。这篇文章总结如何删除链表中相同的元素。

题目原文

编写程序实现：建立一个单链表，然后删除单链表中“重复”的节点，使操作之后的单链表中只留下不同的结点，最后输出单链表中所有结点。

题目解析

需求很清晰，就是要删除重复元素，然后输出剩余不重复的元素即可。此外单链表的创建这里就不演示了，若是不想自己创建单链表的实现类，这个文章里可以直接去复制单链表的实现类然后直接使用即可。单链表的实现

错误的解决示例

这是一种很容易想到的解决方案，但是该方案却是不对的，且可能写完了自己都发现不了这种方案是错的，因为笔者开始就是这么写的，来一起看下这个错误的示范吧。

    //删除链表中相同的元素:错误示范
    public static void deleteRepeat(NewLinkedTable linkedTable) throws Exception{
        if(linkedTable.isEmpty())
            throw new Exception("链表为空");
        //遍历删除
        for(int i=0;i<linkedTable.length();i++){
            for(int j=i+1;j<linkedTable.length();j++){
                if(linkedTable.get(i).equals(linkedTable.get(j))){
                    linkedTable.remove(j);
                }
            }
        }
    }

1).错误思路

我们想要删除一个链表中的重复元素，那么只需要将每一个元素都和其他元素比较即可，当有其他数据元素和原先数据元素相同时，就将其他元素删除，那么最后就可以实现删除重复元素的效果。不过这种方案明显有缺陷，就是每个元素都去和其他所有数据元素比较，明显不合理，这样会有重复比较的情况出现，假设有5个元素，那么第一个元素首先会合其他所有元素比较，若是到第二个元素时还和其他所有元素比较的话，显然他和第一个元素比较就是多余的了因为之前比较过了。所以我们每次只需将当前元素和他之后的元素比较即可。这样就产生了上面的代码。假设链表有五个元素，那么删除的逻辑就是这样的，如下图（请忽略这卑劣的画技）：

2).测试该错误方案

下面创建一个单链表（使用的是这里的单链表实现：单链表的实现），然后往单链表中插入一些元素，调用该方法进行测试。

测试结果如下图所示：

上方代码使用头插法往链表里插入了8个数据，其中有每个数据都是有相同值，调用去重方法后都是只保留了一个，测试得出结果发现去重正确，并没有什么问题。那么秉着严谨的精神，我们再测试下另一种场景：连续重复的场景，如下：

这时就出现问题了，去重后的单链表依然拥有重复值，说明上方实现的去重代码有问题。下面分析下这种去重实现失败的原因。

3).分析去重失败原因

为什么会出现这种有的情况可以实现去重，有的情况又去重失败呢？仔细思考下就会发现问题所在，首先明确在测试第一种场景时成功实现了去重，说明这种情况下逻辑没有问题，问题在于第二种出现连续重复值的场景，当我们删除了一个元素时，删除的元素位置以后的元素相当于是前移了一位的，如下图，若是我们删除的是第三位的链表元素，删除完后接下来的比较理论上是应该再去与第四位的4比较，但是当我们删除3时，4所在的位置就成了第三位，这时程序继续运行比较的是第四位但是4已经变成第三位了5才是第四位，那么就是与5比较，这样正好就把相邻的元素遗漏了，若是相邻元素出现重复，则会去重失败。

正确的解决示例

上面已经分析了错误的原因，那么问题已经清楚，解决起来其实就很容易了，主体代码不动，我们只需要在每次成功删除元素时，再重新比较下当前下标的元素即可，应用在代码里只需要加一行代码即可实现，如下：

//删除链表中相同的元素:正确示范
    public static void deleteRepeat2(NewLinkedTable linkedTable) throws Exception{
        if(linkedTable.isEmpty())
            throw new Exception("链表为空");
        //遍历删除
        for(int i=0;i<linkedTable.length();i++){
            for(int j=i+1;j<linkedTable.length();j++){
                if(linkedTable.get(i).equals(linkedTable.get(j))){
                    linkedTable.remove(j);
                    j--;                                                              //只增加了这一行代码
                }
            }
        }
    }

总结

这种删除重复元素的解决方案，同样适用于顺序表，所以这种方法适用于所有使用线性表结构存储数据的去重。为什么会适用所有线性表的去重呢？因为线性表的逻辑结构都是连续的，逻辑连续就保证了当删除一个元素时，需要将删除元素的前一个和后一个数据元素在逻辑上连接起来。所以我们用这种方法可以实现对所有线性表的去重操作。不过这种方法对于逻辑上不连续的树、图显然是不适用的。