Remove Duplicates from Unsorted List
Write code to remove duplicates from an unsorted linked list.
Example
Given 1->3->2->1->4.
Return 1->3->2->4
Challenge
(hard) How would you solve this problem if a temporary buffer is not allowed? In this case, you don't need to keep the order of nodes.
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 | /** * Definition for ListNode * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { /** * @param head: The first node of linked list. * @return: head node */ public ListNode removeDuplicates(ListNode head) { // Write your code here HashSet<Integer> hash = new HashSet<Integer>(); ListNode cur = head; if (head == null) { return head; } hash.add(cur.val); while (cur.next != null) { if (hash.contains(cur.next.val)) { cur.next = cur.next.next; } else { hash.add(cur.next.val); cur = cur.next; } } return head; } } |