Skip to content

Instantly share code, notes, and snippets.

@Julie728
Created June 24, 2014 00:38
Show Gist options
  • Save Julie728/204962f5bf5ff17026a9 to your computer and use it in GitHub Desktop.
Save Julie728/204962f5bf5ff17026a9 to your computer and use it in GitHub Desktop.
CareerCup 2.1 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?
import java.util.HashSet;
public class Solution {
public static void deleteDuplicates_HashSet(Node head){
HashSet<Integer> nodeSet = new HashSet<Integer>();
Node prev = null;
while(head != null){
if(nodeSet.contains(head.data)){
prev.next = head.next;
}
else{
nodeSet.add(head.data);
prev = head;
}
head = head.next;
}//end of while
}//end of deleteDuplicates_HashSet
//iterate with two pointers:
//1.current which iterate through the linked list
//2. runner which checks all subsequent node for duplicates
public static void deleteDuplicates_runner(Node head){
Node cur = head;
while(cur != null){
Node runner = cur;
while(runner.next != null){
if(cur.data == runner.next.data){
runner.next = runner.next.next;
}
else{
runner = runner.next;
}
}//end of while runner
cur = cur.next;
}//end of while cur
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment