# Remove Duplicates from Unsorted List ### Source - [Remove duplicates from an unsorted linked list - GeeksforGeeks](http://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list/) ~~~ Write a removeDuplicates() function which takes a list and deletes any duplicate nodes from the list. The list is not sorted. For example if the linked list is 12->11->12->21->41->43->21, then removeDuplicates() should convert the list to 12->11->21->41->43. If temporary buffer is not allowed, how to solve it? ~~~ ### 題解1 - 兩重循環 Remove Duplicates 系列題，之前都是已排序鏈表，這個題為未排序鏈表。原題出自 *CTCI* 題2.1。 最容易想到的簡單辦法就是兩重循環刪除重復節點了，當前遍歷節點作為第一重循環，當前節點的下一節點作為第二重循環。 ### Python ~~~ """ Definition of ListNode class ListNode(object): def __init__(self, val, next=None): self.val = val self.next = next """ class Solution: """ @param head: A ListNode @return: A ListNode """ def deleteDuplicates(self, head): if head is None: return None curr = head while curr is not None: inner = curr while inner.next is not None: if inner.next.val == curr.val: inner.next = inner.next.next else: inner = inner.next curr = curr.next return head ~~~ ### C++ ~~~ /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: head node */ ListNode *deleteDuplicates(ListNode *head) { if (head == NULL) return NULL; ListNode *curr = head; while (curr != NULL) { ListNode *inner = curr; while (inner->next != NULL) { if (inner->next->val == curr->val) { inner->next = inner->next->next; } else { inner = inner->next; } } curr = curr->next; } return head; } }; ~~~ ### Java ~~~ /** * Definition for ListNode * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { /** * @param ListNode head is the head of the linked list * @return: ListNode head of linked list */ public static ListNode deleteDuplicates(ListNode head) { if (head == null) return null; ListNode curr = head; while (curr != null) { ListNode inner = curr; while (inner.next != null) { if (inner.next.val == curr.val) { inner.next = inner.next.next; } else { inner = inner.next; } } curr = curr.next; } return head; } } ~~~ ### 源碼分析 刪除鏈表的操作一般判斷`node.next`較為合適，循環時注意`inner = inner.next`和`inner.next = inner.next.next`的區別即可。 ### 復雜度分析 兩重循環，時間復雜度為 O(12n2)O(\frac{1}{2}n^2)O(21n2), 空間復雜度近似為 O(1)O(1)O(1). ### 題解2 - 萬能的 hashtable 使用輔助空間哈希表，節點值作為鍵，布爾值作為相應的值（是否為布爾值其實無所謂，關鍵是鍵）。 ### Python ~~~ """ Definition of ListNode class ListNode(object): def __init__(self, val, next=None): self.val = val self.next = next """ class Solution: """ @param head: A ListNode @return: A ListNode """ def deleteDuplicates(self, head): if head is None: return None hash = {} hash[head.val] = True curr = head while curr.next is not None: if hash.has_key(curr.next.val): curr.next = curr.next.next else: hash[curr.next.val] = True curr = curr.next return head ~~~ ### C++ ~~~ /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: head node */ ListNode *deleteDuplicates(ListNode *head) { if (head == NULL) return NULL; // C++ 11 use unordered_map // unordered_map<int, bool> hash; map<int, bool> hash; hash[head->val] = true; ListNode *curr = head; while (curr->next != NULL) { if (hash.find(curr->next->val) != hash.end()) { ListNode *temp = curr->next; curr->next = curr->next->next; delete temp; } else { hash[curr->next->val] = true; curr = curr->next; } } return head; } }; ~~~ ### Java ~~~ /** * Definition for ListNode * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { /** * @param ListNode head is the head of the linked list * @return: ListNode head of linked list */ public static ListNode deleteDuplicates(ListNode head) { if (head == null) return null; ListNode curr = head; HashMap<Integer, Boolean> hash = new HashMap<Integer, Boolean>(); hash.put(curr.val, true); while (curr.next != null) { if (hash.containsKey(curr.next.val)) { curr.next = curr.next.next; } else { hash.put(curr.next.val, true); curr = curr.next; } } return head; } } ~~~ ### 源碼分析 刪除鏈表中某個節點的經典模板在`while`循環中體現。 ### 復雜度分析 遍歷一次鏈表，時間復雜度為 O(n)O(n)O(n), 使用了額外的哈希表，空間復雜度近似為 O(n)O(n)O(n). ### Reference - [Remove duplicates from an unsorted linked list - GeeksforGeeks](http://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list/) - [ctci/Question.java at master · gaylemcd/ctci](https://github.com/gaylemcd/ctci/blob/master/java/Chapter%202/Question2_1/Question.java)