No.82 删除排序链表中的重复元素②（Medium）

题目描述

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。

示例：

思路

该题需要删除所有重复的元素，一个都不保留。

递归思路

终止条件

仅有0个元素或者1个元素；

单层逻辑

传入head结点，判断head与head.next的值是否相同：
如果不同：head指向下一层递归的返回值
例如，在示例中，传入结点2，因为2和3不同，所以2到3的指向需要保留，因此是2->（3以后形成的递归返回）

如果相同：因为是排好序的链表，所以相同的值必定相邻。往后遍历，直到找到不同的值，返回该值对应的结点进行递归的返回值。
例如，在示例中，传入结点3，因为3和下一个3相同，那么一直往后找，直到找到4，返回4以后形成的递归返回。这里注意，不是直接返回4，而是4的递归返回，因为4也可能和后边结点重复。

递归代码

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // 终止条件
        // 没有结点或者只有一个结点了，当只有一个结点时，必然不会出现重复，直接返回该结点即可
        if (head == null || head.next == null) {
            return head;
        }
        // 相邻的两个值不同，则保留向后的指向
        if (head.val != head.next.val) {
            head.next = deleteDuplicates(head.next);
            return head;
        }
        // 用temp来找到不相同的结点
           ListNode temp = head;
        // 记得要加 temp != null, 否则temp.next会出现空指针异常
        while (temp != null && temp.val == head.val) {
            temp = temp.next;
        }
        // 注意不是head.next = deleteDuplicates(temp);
        // 因为值相同时，head.next这个引用是要丢弃的。
        return deleteDuplicates(temp);
    }
}

非递归思路

定义一个tail指针用来指向当前已经形成的链表的最后一个结点，不断通过遍历后续的结点来添加不重复的结点，并且将tail重新指向最后的结点。

如果head.val == head.next.val;
head = head.next; 循环，直到找到不相等的结点，让tail 指向 head

例如:1- > 2 -> 3 -> 3 -> 4 -> 4 ->5
dummy -> 1 ， tail 指向1, head指向2
dummy -> 1-> 2, tail 指向2, head指向3
dummy -> 1-> 2， tail指向2，head指向第二个3，
dummy -> 1-> 2， tail指向2，head指向第一个4，
dummy -> 1-> 2， tail指向2，head指向第二个4，
dummy -> 1 -> 2 -> 5, tail指向5，head指向5,

非递归代码

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (head != null) {
            if (head.next == null || head.val != head.next.val) {
                tail.next = head;
                tail = head;
            }
            // 例如，碰到两个3的时候，循环后head指向最后一个3，但是这个3是不需要的
            // 因此还要在循环结束后调用head = head.next; 让其指向4
            while (head.next != null && head.val == head.next.val) {
                head = head.next;
            }
            head = head.next;
        }
        // 最后让tail指向null
        tail.next = null;
        return dummy.next;
    }
}