Remove duplicates from an unsorted linked list
978 ワード
Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?
Solution:
public ListNode removeDuplicate(ListNode head) {
ListNode dummy = head;
Set<Integer> set = new HashSet<Integer>();
ListNode pre = null;
while(head!=null) {
if(set.add(head.val)) {
pre = head;
} else {
pre.next = head.next;
}
head = head.next;
}
return dummy;
}
Followup
public ListNode removeDupsWithoutBuffer(ListNode head) {
ListNode cur = head;
while(cur!=null) {
ListNode n = cur;
while(n.next!=null) {
if(n.next.val == cur.val) {
n.next = n.next.next;
} else {
n = n.next;
}
}
cur = cur.next;
}
return head;
}