【题目】
给定一个无序单链表的头节点head,删除其中值重复出现的节点。
例如：1->2->3->3->4->4->2->1->1->null,删除值重复的节点之后为1->2->3->4->null.
请按一下要求实现两种方法
1.如果链表长度为N,时间复杂度达到O(N)
2.额外空间复杂度为O(1)
【解析】
方法一：利用哈希表，时间复杂度为O(N)，额外空间复杂度为O(N)
具体实现：
1.生成一个哈希表，因为头结点是不用删除的节点，所以将头节点值放入哈希表。
2.从头节点的下一个节点开始往后遍历节点，假设当前遍历到cur节点，先检查cur的值是不是在哈希表中，如果在，说明cur节点的值是之前出现过的，就将cur节点删除，删除的方式是将最近一个没有被删除的节点pre链接到cur的下一个节点，即pre.next = cur.next.如果不在，将cur节点的值加入哈希表，同时令pre=cur,即更新最近一个没有被删除的节点

package 删除无序链表中的值重复出现的节点;

import java.util.HashSet;

public class Main {

    
    /**节点类*/
    public static class Node{
        public int value;
        public Node next;
        
        public Node(int data){
            this.value = data;
        }
    }
    
    /**哈希表删除重复节点*/
    
    public static void removeRep1(Node head){
        if (head == null) {
            return;
        }
        HashSet<Integer> set = new HashSet<Integer>();
        Node pre = head;
        Node cur = head.next;
        set.add(head.value);
        
        while (cur != null) {
            if (set.contains(cur.value)) {
                pre.next = cur.next;
            } else {
                set.add(cur.value);
                pre = cur;
            }
            cur = cur.next;
        }
        
        
        
    }
    
    
    
    public static void main(String[] args) {
        Node head = new Node(1);
        Node head2 = new Node(2);
        Node head3 = new Node(3);
        Node head4 = new Node(3);
        Node head5 = new Node(5);
        Node head6 = new Node(5);
        Node head7 = new Node(5);
        Node head8 = new Node(5);
        head.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head5;
        head5.next = head6;
        head6.next = head7;
        head7.next = head8;
        removeRep1(head);
        print(head);
        
    }



    private static void print(Node head) {
        if (head == null) {
            return ;
        } 
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.value+"->");
            cur = cur.next;
        }
        System.out.println();
        
    }
    
    
    
}

方法二：

image.png

/**选择删除节点*/
    public static void removeRep2(Node head){
        Node cur = head;
        Node pre = null;
        Node next = null;
        while (cur != null) {
            pre = cur;
            next = cur.next;
            while (next != null) {
                if (cur.value == next.value) {
                    pre.next = next.next;
                } else {
                    pre = next;
                }
                next = next.next;
            }
            cur = cur.next;
        }
    }