# Remove Duplicates from Unsorted List

## Question

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:
"""
@return: A ListNode
"""
return None

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



### C++

/**
* Definition of ListNode
* class ListNode {
* public:
*     int val;
*     ListNode *next;
*     ListNode(int val) {
*         this->val = val;
*         this->next = NULL;
*     }
* }
*/
class Solution {
public:
/**
*/
if (head == NULL) return NULL;

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;
}

}
};


### Java

/**
* Definition for ListNode
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
/**
*/
public static ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;

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;
}

}
}


## 题解2 - 万能的 hashtable

### Python

"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@return: A ListNode
"""
return None

hash = {}
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



### C++

/**
* Definition of ListNode
* class ListNode {
* public:
*     int val;
*     ListNode *next;
*     ListNode(int val) {
*         this->val = val;
*         this->next = NULL;
*     }
* }
*/
class Solution {
public:
/**
*/
if (head == NULL) return NULL;

// C++ 11 use unordered_map
// unordered_map<int, bool> hash;
map<int, bool> hash;
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;
}
}

}
};


### Java

/**
* Definition for ListNode
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
/**
*/
public static ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;

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;
}
}

}
}