Remove duplicates from an unsorted linked list | GeeksforGeeks
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2002.%20Linked%20Lists/Q2_01_Remove_Dups/QuestionB.java
public static void deleteDups(LinkedListNode head) {
LinkedListNode current = head;
while (current != null) {
/* Remove all future nodes that have the same value */
LinkedListNode runner = current;
while (runner.next != null) {
if (runner.next.data == current.data) {
runner.next = runner.next.next;
} else {
runner = runner.next;
}
}
current = current.next;
}
}
public static void deleteDups(LinkedListNode head) {
if (head == null) return;
LinkedListNode previous = head;
LinkedListNode current = previous.next;
while (current != null) {
// Look backwards for dups, and remove any that you see.
LinkedListNode runner = head;
while (runner != current) {
if (runner.data == current.data) {
LinkedListNode tmp = current.next;
previous.next = tmp;
current = tmp;
/* We know we can't have more than one dup preceding
* our element since it would have been removed
* earlier. */
break;
}
runner = runner.next;
}
/* If runner == current, then we didn't find any duplicate
* elements in the previous for loop. We then need to
* increment current.
* If runner != current, then we must have hit the �break�
* condition, in which case we found a dup and current has
* already been incremented.*/
if (runner == current) {
previous = current;
current = current.next;
}
}
}
Read full article from Remove duplicates from an unsorted linked list | GeeksforGeeks
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.
public static void deleteDups(LinkedListNode n) {
HashSet<Integer> set = new HashSet<Integer>();
LinkedListNode previous = null;
while (n != null) {
if (set.contains(n.data)) {
previous.next = n.next;
} else {
set.add(n.data);
previous = n;
}
n = n.next;
}
}
Follow Up: No Buffer Allowed
public static void deleteDups(LinkedListNode head) {
LinkedListNode current = head;
while (current != null) {
/* Remove all future nodes that have the same value */
LinkedListNode runner = current;
while (runner.next != null) {
if (runner.next.data == current.data) {
runner.next = runner.next.next;
} else {
runner = runner.next;
}
}
current = current.next;
}
}
public static void deleteDups(LinkedListNode head) {
if (head == null) return;
LinkedListNode previous = head;
LinkedListNode current = previous.next;
while (current != null) {
// Look backwards for dups, and remove any that you see.
LinkedListNode runner = head;
while (runner != current) {
if (runner.data == current.data) {
LinkedListNode tmp = current.next;
previous.next = tmp;
current = tmp;
/* We know we can't have more than one dup preceding
* our element since it would have been removed
* earlier. */
break;
}
runner = runner.next;
}
/* If runner == current, then we didn't find any duplicate
* elements in the previous for loop. We then need to
* increment current.
* If runner != current, then we must have hit the �break�
* condition, in which case we found a dup and current has
* already been incremented.*/
if (runner == current) {
previous = current;
current = current.next;
}
}
}
Read full article from Remove duplicates from an unsorted linked list | GeeksforGeeks