删除链表中重复的元素解法分析

链表的操作非常常见，也是面试中经常会被问道的问题。对于链表重复元素的删除，有两个变体，现在总结如下。
链表代码如下：

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

1.删除重复元素，所有元素只保留一次。

 * @description 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
 * 示例 1:
 * 输入: 1->1->2
 * 输出: 1->2
 * 示例 2:
 * 输入: 1->1->2->3->3
 * 输出: 1->2->3
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list

这个问题的解法非常简单，只需要定义一个指针然后while循环即可。

    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (null!=cur&&null!=cur.next){
            if(cur.val == cur.next.val){
                if(null != cur.next.next){
                    cur.next = cur.next.next;
                }else {
                    cur.next = null;
                }
            }else {
                cur = cur.next;
            }
        }
        return head;
    }

定义一个指针cur，然后循环判断cur.value和cur.next.value，如果相等，那么就将后面重复元素移除。如果不等，则指针后移。

2.删除全部重复的元素，只保留没有重复的元素。

*@description
 * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
 * 示例 1:
 * 输入: 1->2->3->3->4->4->5
 * 输出: 1->2->5
 * 示例 2:
 * 输入: 1->1->1->2->3
 * 输出: 2->3
 * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii

本文需要重点关注的是这个变体，因为问题1的解法很简单。没什么特别的。但是加上了将全部重复的数字都去除这个条件之后，难度瞬间增加了不少。你需要考虑两个问题：

• 如果链表头就是重复的数字怎么办
• 如何移动比较链表，删除元素？

参考 https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/solution/chao-qing-xi-tu-jie-san-zhi-zhen-fa-by-justdo1t/

第一，对于表头重复的问题，那么最简单的办法就是在表头添加一个元素，加入链表。之后在链表遍历完之后，返回哨兵的next。这是一个非常好的办法，简直是以后解决链表类问题的套路之一。

    ListNode cur = new ListNode(0);
        cur.next = head;
        head = cur;

仅仅三行代码就搞定了。
第二，对于如何移动比较的问题，此时发现，用一个指针无论如何也无法实现题目的需求了。此时看到了参考文档中的三指针法。现在将文章中的内容发下来：
除了哨兵之外，需要定义一个left和一个right两个指针。

image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png

先用right和right下一个元素比较，如果相等，则left移动。之后循环判断left和right两个指针是否指向同一个元素。如果相等，则说明没有相同的元素。哨兵cur向后移动。反之，则说明存在相同的元素，哨兵则将当前next指针指向right.next,将重复元素都删除。完整算法如下：

    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = new ListNode(0);
        cur.next = head;
        head = cur;
        ListNode left,right;
        while (null!=cur&&null!=cur.next){
            left = cur.next;
            right = cur.next;
            while (null!=right.next&&right.next.val==left.val){
                right = right.next;
            }
            if(right == left){
                cur = cur.next;
            }else {
                cur.next = right.next;
            }
        }
        return head.next;
    }

三指针法，也是一个经典的算法。在后续面链表相关问题的时候，又是一个新套路。