题解 | #删除有序链表中重复的元素-II#遍历｜递归

解法1:遍历然后删除所有的

用一个临时变量conpared来存储当前需要比较的值

如果发现这个值是重复的，那么就用while循环找到最后一个重复的节点，直接删除这一堆重复的点prev.next = current.next;

如果没有发现重复的，那就prev继续往下去遍历

每一轮结束都要重新让current指向prev的下一个节点

import java.util.*;

public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prevOfHead = new ListNode(-1001);
        ListNode prev = prevOfHead;
        prev.next = head;
        ListNode current = head;
        int comparedValue;
        while (current != null && current.next != null) {
            comparedValue = current.val;
            if (current.next.val == comparedValue) {
                // find the last duplicated node 
                while (current.next != null && current.next.val == comparedValue) {
                    current = current.next;
                }
            // delete all duplicated node by link prev with next of last duplicated node
                prev.next = current.next;
            } else {
                prev = prev.next;
            }
            
            if (prev != null) {
                current = prev.next;
            }
        }
        return prevOfHead.next;
    }
}

解法2:递归

import java.util.*;
public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prevOfHead = new ListNode(-1001);
        prevOfHead.next = head;
        int comparedValue = head.val;
	  // if head is duplicate node, then move head to the next node with diff value
        if (head.val == head.next.val) {
            while (head != null && head.val == comparedValue) {
                head = head.next;
            }
            prevOfHead.next = deleteDuplicates(head);
        } else {
		  //if node is not duplicate node, then just handle next node
            head.next = deleteDuplicates(head.next);
        }
        return prevOfHead.next;
    }
}

解法3:哈希表

import java.util.*;
public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        Set<Integer> visited = new HashSet<Integer>();
        ListNode prevOfHead = new ListNode(-1001);
        prevOfHead.next = head;
        ListNode current = head;
        ListNode prev = prevOfHead;
        while (current != null) {
            visited.add(current.val);
		  // if current is duplicated node, then move current util the val is different;
            if (current.next != null && visited.contains(current.next.val)) {
                while(current.next != null && visited.contains(current.next.val)) {
                    current = current.next;
                }
                prev.next = current.next;
                current = prev.next;
            } else {
                prev = current;
                current = current.next;
            }
        }
        return prevOfHead.next;
    }
}

时间复杂度：O(n)

空间复杂度：O（n）

个人感觉没有必要用哈希来做，因为这个链表是顺序存储的，因为用一个临时变量就够了

甚至不需要临时变量，一直用current.val == current.next.val 来判断就可以了