2.1---删除链表中重复元素（CC150）

分成两种，1种开了额外空间，临时缓冲区，一种没有开

import java.util.HashSet;

import java.util.Set;

class ListNode{

    int data;

    ListNode next;

}

public class Solution{

    public static void main(String[] args){

        ListNode head = new ListNode();

        head.data = 1;

        ListNode node = new ListNode();

        node.data = 1;

        head.next = node;

        ListNode tmp = head;

        while(tmp != null){

            System.out.println(tmp.data);

            tmp = tmp.next;

        }

        tmp = deleteDuplication2(head);

        System.out.println("delete");

        while(tmp != null){

            System.out.println(tmp.data);

            tmp = tmp.next;

        }

    }

    //使用了缓冲区，开了额外空间

    public static ListNode deleteDuplication(ListNode head){

        if(head == null) return head;

        Set<Integer> set = new HashSet();

        ListNode cur = head;

        set.add(cur.data);

        ListNode pre = cur;

        cur = cur.next;

        while(cur != null){

            if(!set.contains(cur.data)){

                set.add(cur.data);

            }

            else{

                pre.next = cur.next;

            }

            pre = pre.next;

            cur = cur.next;

        }

        return head;

    }

    //不使用额外空间，不开缓冲区

    public static ListNode deleteDuplication2(ListNode head){

        if(head == null) return head;

        ListNode master = head;

        while(master != null){

            ListNode pre = master;

            ListNode cur = master.next;

            int value = master.data;

            while(cur != null){

                if(cur.data == value){

                    pre.next = cur.next;

                    cur = pre.next;

                }else{

                    cur.next = cur;

                    pre.next = pre;

                }

            }

            master = master.next;

        }

        return head;

    }

}