Tuesday, December 23, 2014

Write code to remove duplicates from an unsorted linked list. [With and without using a temporary buffer]

Q. Write code to remove duplicates from an unsorted linked list.

AABSSSDDAABBDSA

ABSD

Algorithm (doing it without buffer):

1. Maintain three pointers.
2. First is the slowest.
3. Second and third start from first's position on each iteration and go to the end to remove the duplicates of the value currently in the node represented by first pointer.

Source:

```public class LinkedList <T>{

class Node{
Node next;
T value;

Node(T value){this.value = value;}
}

while(t.next!=null){t = t.next;}
t.next = new Node(value);
}

public boolean isEmpty(){
}

@Override
public String toString(){
StringBuilder bf = new StringBuilder();
while(t!=null){
bf.append(t.value);
t = t.next;
}
return bf.toString();
}
}```

```import java.util.HashSet;

public class Code{

return ll;
}

HashSet buffer = new HashSet();
while(t1!=null){
if(!buffer.contains(t1.value)){
t2 = t1;
t1 = t1.next;
}else{
while(buffer.contains(t1.value)){
t1 = t1.next;
if(t1==null)break;
}
t2.next = t1;
}
}
}

while(t0!=null){
t1 = t0;
t2 = t1.next;

Object value = t1.value;
while(t2!=null){
if(t2.value == value){
while(t2.value == value){
t2 = t2.next;
if(t2==null)break;
}
t1.next = t2;
}else{
t1.next = t2;
}
t1 = t2;
if(t2!=null) t2 = t2.next;
}
t0 = t0.next;
}
}

public static void testWithBuffer(String s){
removeDuplicatesUsingBuffer(ll);
System.out.println(ll.toString());
}

public static void testWithoutBuffer(String s){
removeDuplicatesWihoutBuffer(ll);
System.out.println(ll.toString());
}
public static void main(String[] args){

System.out.println("Using a Buffer: ");
testWithBuffer("a");
testWithBuffer("aa");
testWithBuffer("azzzxxxa");
testWithBuffer("abcdef");
testWithBuffer("www.codebytes.in");
testWithBuffer("");

System.out.println("\nWithout using a buffer: ");
testWithoutBuffer("a");
testWithoutBuffer("aa");
testWithoutBuffer("azzzxxxa");
testWithoutBuffer("abcdef");
testWithoutBuffer("www.codebytes.in");
testWithoutBuffer("");
}
}```

Output:

Using a Buffer:
a
a
abcdef
azx
abcdef
FOLW UP
w.codebytsin

Without using a buffer:
a
a
abcdef
azx
abcdef
FOLW UP
w.codebytsin