First Unique Number in Data Stream

Java

public class Solution {
		class ListNode {
			int num;
			ListNode prev, next; //定义为双向指针
			ListNode(int num) {
			this.num = num;
			}
		}
		
		ListNode head, tail;
		//每一个数字在LinkedList中指向的节点是哪一个
		Map<Integer, ListNode> map;
		//记录数字是否访问过
		Set<Integer> seen;
		
		public int firstUniqueNumber(int[] nums, int number) {
			head = new ListNode(-1); //dummy
			tail = head;
			map = new HashMap<>();
			seen = new HashSet<>();
			
		for (int num : nums) {
				addNumber(num);
				if (num == number) { //在之前找答案
					return getFirstUnique();
				}
			}
			return -1;
		}
		
		private void addNumber(int num) {
			//没出现过
			if (!seen.contains(num)) {
				seen.add(num);
				//add new node to linkedList
				ListNode node = new ListNode(num);
				tail.next = node; //append 在 tail 后边
				node.prev = tail;
				tail = node;//tail 更新一下
				//update map
				map.put(num, node);
			} else if (map.containsKey(num)) { //避免有第三个数出现，不能直接用else   ？？？？？？
				//出现过
				//delete node from linkedList
				ListNode node = map.get(num);
				ListNode prev = node.prev;
				ListNode next = node.next; //出现 .next 都需要判断corner case
				prev.next = next;
		//next节点有可能是null
				if (next != null) {
					next.prev = prev;
				} else {
					tail = prev;
				}
				//update map
				map.remove(num); //不remove 会怎么样？
			}
		}
		
		private int getFirstUnique() {
		return head.next == null ? -1 : head.next.num;
		}
}