138 删除无序链表中值重复出现的节点
Table of Contents

ac

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


class Node{
    int val;
    Node next;

    public Node(int val) {
        this.val = val;
        this.next = null;
    }
}


public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long)Math.pow(2,29);

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        Node head = null;
        Node tail = null;
        for(int i=0;i<n;i++){
            int val = sc.nextInt();
            if(head == null){
                head = new Node(val);
                tail = head;
            }else {
                Node tmp = new Node(val);
                tail.next = tmp;
                tail = tmp;
            }
        }
        Node newHead = distinct(head);
        printNode(newHead);
        System.out.println();
    }

    /**
     * 时间复杂度O(N), 空间复杂度O(N)
     */
    static Node distinct(Node head){
        if(head == null || head.next == null){
            return head;
        }
        Set<Integer> se = new HashSet<>();
        se.add(head.val);
        Node p = head.next;

        Node newHead = head;
        newHead.next = null;
        Node newTail = newHead;

        while (p != null){
            Node pNext= p.next;
            if(!se.contains(p.val)){
                newTail.next = p;
                newTail = p;
                newTail.next = null;

                se.add(p.val);
            }
            p = pNext;
        }
        return newHead;
    }

    static void printNode(Node node){
        if(node == null){
            return;
        }
        boolean flag = true;
        Node p = node;
        while (p != null){
            Node pNext = p.next;
            if(flag){
                System.out.print(p.val);
                flag = false;
            }else {
                System.out.print(" " + p.val);
            }
            p = pNext;
        }
    }

}
/*
5
1 3 2 3 1

1 3 2
*/