Lintcode 685. First Unique Number in Data Stream

Given a continuous stream of numbers, write a function that returns the first unique number whenever terminating number is reached(include terminating number). If there no unique number before terminating number or you can't find this terminating number, return -1.

Example

Example1

Input: 
[1, 2, 2, 1, 3, 4, 4, 5, 6]
5
Output: 3

Example2

Input: 
[1, 2, 2, 1, 3, 4, 4, 5, 6]
7
Output: -1

Solution:
HashMap + Linked list

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

public class Solution {     /**      * @param nums: a continuous stream of numbers      * @param number: a number      * @return: returns the first unique number      */     public int firstUniqueNumber(int[] nums, int number) {         // Write your code here         if (nums == null || nums.length == 0) {             return -1;         }           MyLinkedList canidateList = new MyLinkedList();         Map<Integer, ListNode> numToNodeMap = new HashMap<>();         for (int num : nums) {             insert(num, canidateList, numToNodeMap);             if (num == number) {                 if (canidateList.isEmpty()) {                     return -1;                 } else {                     return canidateList.getFirst().val;                 }             }         }           return -1;     }       private void insert(int num, MyLinkedList list, Map<Integer, ListNode> map) {         if (map.containsKey(num)) {             // need to distiguish the 2nd time or 2+ times             if (map.get(num) != null) {                 list.remove(map.get(num));                 map.put(num, null);             }         } else {             ListNode node = list.append(num);             map.put(num, node);         }     } }   class ListNode {     ListNode next, prev;     int val;     public ListNode(int val) {         this.val = val;         next = prev = null;     } }   class MyLinkedList {     private ListNode dummyHead;     private ListNode dummyTail;     public MyLinkedList() {         dummyHead = new ListNode(-1);         dummyTail = new ListNode(-1);           dummyHead.next = dummyTail;         dummyTail.prev = dummyHead;     }       public ListNode getFirst() {         return dummyHead.next;     }       public boolean isEmpty() {         return dummyHead.next == dummyTail;     }       public void remove(ListNode node) {         ListNode prevNode = node.prev;         ListNode nextNode = node.next;         prevNode.next = nextNode;         nextNode.prev = prevNode;     }       public ListNode append(int num) {         ListNode currNode = new ListNode(num);         ListNode prevNode = dummyTail.prev;         prevNode.next = currNode;         currNode.next = dummyTail;         dummyTail.prev = currNode;         currNode.prev = prevNode;           return currNode;     } }