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