Skip to content

Instantly share code, notes, and snippets.

@philipjkim
Created December 23, 2016 01:35
Show Gist options
  • Save philipjkim/286579a9b71dc1075218c2befe81939e to your computer and use it in GitHub Desktop.
Save philipjkim/286579a9b71dc1075218c2befe81939e to your computer and use it in GitHub Desktop.
Removing duplications in a single linked list
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