Created
December 23, 2016 01:35
-
-
Save philipjkim/286579a9b71dc1075218c2befe81939e to your computer and use it in GitHub Desktop.
Removing duplications in a single linked list
This file contains hidden or 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 bar.foo; | |
public class LinkedList { | |
Node head; | |
// Push i to the first index of the linked list, so i becomes the new head. | |
void push(int i) { | |
Node n = new Node(i); | |
n.next = this.head; | |
this.head = n; | |
} | |
void removeDups() { | |
Node toCompare = this.head; | |
while(toCompare != null) { | |
Node prev = toCompare; | |
Node curr = toCompare.next; | |
while(curr != null) { | |
if (curr.data == toCompare.data) { | |
curr = curr.next; | |
prev.next = curr; | |
} else { | |
prev = curr; | |
curr = curr.next; | |
} | |
} | |
toCompare = toCompare.next; | |
} | |
} | |
class Node { | |
int data; | |
Node next; | |
Node(int data) { | |
this.data = data; | |
} | |
@Override | |
public String toString() { | |
StringBuilder sb = new StringBuilder(); | |
sb.append(this.data); | |
if (this.next != null) { | |
sb.append("->").append(this.next.toString()); | |
} | |
return sb.toString(); | |
} | |
} | |
public static void main(String[] args) { | |
LinkedList l = new LinkedList(); | |
String before = str(l.head); | |
l.removeDups(); | |
printResult(before, str(l.head), "null"); | |
l.push(1); | |
before = str(l.head); | |
l.removeDups(); | |
printResult(before, str(l.head), "1"); | |
l.push(1); | |
before = str(l.head); | |
l.removeDups(); | |
printResult(before, str(l.head), "1"); | |
l.push(2); | |
before = str(l.head); | |
l.removeDups(); | |
printResult(before, str(l.head),"2->1"); | |
l.push(2); | |
l.push(1); | |
before = str(l.head); | |
l.removeDups(); | |
printResult(before, str(l.head),"1->2"); | |
l = new LinkedList(); | |
l.push(2); | |
l.push(1); | |
l.push(2); | |
l.push(1); | |
l.push(1); | |
l.push(2); | |
l.push(3); | |
before = str(l.head); | |
l.removeDups(); | |
printResult(before, str(l.head),"3->2->1"); | |
l = new LinkedList(); | |
l.push(2); | |
for (int i = 0; i < 20; i++) { | |
l.push(1); | |
} | |
l.push(3); | |
before = str(l.head); | |
l.removeDups(); | |
printResult(before, str(l.head),"3->1->2"); | |
} | |
static String str(Node n) { | |
if (n == null) { | |
return "null"; | |
} | |
return n.toString(); | |
} | |
static void printResult(String before, String after, String expected) { | |
System.out.printf("Before: %s, After: %s, Expected: %s\n", before, after, expected); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment