Skip to content

Instantly share code, notes, and snippets.

@XiaoxiaoLi
Last active September 29, 2015 16:16
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save XiaoxiaoLi/8559f31eace496fc6fec to your computer and use it in GitHub Desktop.
Save XiaoxiaoLi/8559f31eace496fc6fec to your computer and use it in GitHub Desktop.
#CC150 #CC150-chap2 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?
package chap2;
import java.util.HashSet;
import java.util.Set;
//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?
public class DeleteDuplicatesInList {
/**
* Use an extra HashSet to store the unique node values. If we see a
* duplicate, remove it.
*
* Time complexity O(n)
*
* Space complexity O(n)
*
* @param n
*/
public static void deleteDuplicatesWithSet(Node n) {
// If we only have one element there is no duplicates
if (n == null || n.next == null) {
return;
}
// Keeps track of the unique elements
Set<Integer> uniqueSet = new HashSet<Integer>();
// Keep track of the previous node in case we need to delete a node
Node prev = n;
while (n != null) {
if (uniqueSet.contains(n.data)) {
// Remove n, the prev node stays the same
prev.next = n.next;
} else {
// Store the data in the uniqueSet, n is then the prev node
uniqueSet.add(n.data);
prev = n;
}
n = n.next;
}
}
/**
* Use two pointers , p1 goes from the front to the end with one sweep, p2
* goes from p1 to the end repeatedly to check and delete any element that
* is the same as the one p1 points to until p1 reaches the end
*
* Time Complexity O(n^2)
*
* Space Complexity O(1) keep?
*
* @param n
*/
public static void deleteDuplicatesWithPointers(Node n) {
if (n == null || n.next == null) {
return;
}
Node p1 = n;
while (p1 != null && p1.next != null) {
Node p2 = p1.next;
Node prev = p1;
while (p2 != null) {
if (p2.data == p1.data) {
// Remove the p2 node, prev stays the same
prev.next = p2.next;
} else {
// p2 becomes the prev node
prev = p2;
}
p2 = p2.next;
}
// If p2 reaches the end, p1 moves one, p2 moves to the node behind
// the new p1
p1 = p1.next;
}
}
/**
* Similar to my solution but this is the book's solution. Use two pointers
* , current iterates through the list. runner checks all subsequent nodes
* for duplicates. In the code, runner = current, and it checks the value of
* runner.next and current. Makes it easier to determine the loop conditions
*
* Time Complexity O(n^2)
*
* Space Complexity O(1)
*
* @param n
*/
public static void deleteDuplicatesWithRunner(Node head) {
if (head == null || head.next == null) {
return;
}
Node current = head;
while (current != null) {
Node runner = current;
while (runner.next != null) {
// Compare the runner.next with current
if (runner.next.data == current.data) {
// Remove runner.next
runner.next = runner.next.next;
} else {
runner = runner.next;
}
}
current = current.next;
}
}
public static void main(String args[]) {
DeleteDuplicatesInList.Node n = new Node(1);
// n.appendToTail(2);
n.appendToTail(2);
n.appendToTail(1);
n.appendToTail(2);
System.out.println("Original : " + n.toString());
deleteDuplicatesWithRunner(n);
System.out.println("After deleting duplicates: " + n.toString());
}
// Another solution: ask if the order matters, if not, sort the list in O(nlgn) time and delete duplicates in one sweep in O(n) time. But I don't know about sorting linkedList, can you do that in place?
// https://gist.github.com/iwilbert/155842366920552262d7 and https://gist.github.com/habina/3896531754d629b2032f uses sorting
/**
* Implementation of a simple LinkedList
*
* @author xl16
*
*/
static class Node {
Node next = null;
int data;
public Node(int d) {
data = d;
}
public void appendToTail(int d) {
Node end = new Node(d);
Node n = this;
while (n.next != null) {
n = n.next;
}
n.next = end;
}
public String toString() {
Node n = this;
String str = "";
while (n.next != null) {
str += String.valueOf(n.data) + "->";
n = n.next;
}
// The last node
str += String.valueOf(n.data) + "->null";
return str;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment