-
-
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?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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