LinkedList Algos

Remove Duplicates in a LinkedList 

Let's write code to remove duplicates from LinkedList.

Option1 : Temp Storage Not Allowed 

Since no additional Storage allowed, let's have 2 pointers and we compare data of two as we iterate.

static class Node 

{

private Integer data;

private Node next;

public Node(Integer data) {

super();

this.data = data;

}

}

    public static void main( String[] args )

    {

        Node node = new Node(1);

        node.next = new Node(2);

        node.next.next = new Node(3);

        node.next.next.next = new Node(3);

        node.next.next.next.next = new Node(4);

        node.next.next.next.next.next = new Node(5);

        node.next.next.next.next.next.next = new Node(5);

        node.next.next.next.next.next.next.next = new Node(7);

        node.next.next.next.next.next.next.next.next = new Node(8);

        System.out.println("Before ");

        Node printNode = node;

        while(printNode != null)

        {

        System.out.println(printNode.data);

        printNode = printNode.next;

        }

        removeDuplicates(node);

        System.out.println("After ");

        printNode = node;

        while(printNode != null)

        {

        System.out.println(printNode.data);

        printNode = printNode.next;

        }

    }

private static void removeDuplicates(Node node) {

if (node ==null ) return;

Node pointer1 = node;

while(pointer1 != null)

{

Node pointer2 = pointer1;

while(pointer2.next != null)

{

if(pointer1.data == pointer2.next.data)

pointer2.next = pointer2.next.next;

else

pointer2 = pointer2.next;

}

pointer1 = pointer1.next;

}

}

}

Option 2 : Temp Storage Allowed 
With Additional Storage allowed, solution simplifies a lot , you just need to compare each value against temp stored values, here it is :

private static void removeDuplicates(Node node) {

Set<Integer> collected = new HashSet();

Node previous = null;

while(node != null)

{

if(collected.contains(node.data))

{

previous.next = node.next;

}

else

{

collected.add(node.data);

previous = node;

}

node = node.next;

}

}

Find nth to last element in a LinkedList

One of the algorithm is to use 2 pointers separated by distance =n

public class FindNthElement1 

{

static class Node 

{

private Integer data;

private Node next;

public Node(Integer data) {

super();

this.data = data;

}

}

    public static void main( String[] args )

    {

        Node node = new Node(1);

        node.next = new Node(2);

        node.next.next = new Node(3);

        node.next.next.next = new Node(3);

        node.next.next.next.next = new Node(4);

        node.next.next.next.next.next = new Node(5);

        node.next.next.next.next.next.next = new Node(5);

        node.next.next.next.next.next.next.next = new Node(7);

        node.next.next.next.next.next.next.next.next = new Node(8);

        node.next.next.next.next.next.next.next.next.next = new Node(9);

        findnThLastElement(node, 0);

        findnThLastElement(node, 1);

        findnThLastElement(node, 3);

        findnThLastElement(node, 7);

        findnThLastElement(node, 9);

        findnThLastElement(node, 10);

    }

private static void findnThLastElement(Node node, int i) {

Node firstPointer = node;

Node secondPointer = null;

int counter = 0;

while(firstPointer.next!= null)

{

firstPointer = firstPointer.next;

if(secondPointer != null)

secondPointer = secondPointer.next;

++counter;

if(secondPointer == null && counter == i)

secondPointer = node;

if(secondPointer == null && counter > i)

secondPointer = firstPointer;

}

if(secondPointer == null)

System.out.println("No Element found!");

else

System.out.println(secondPointer.data);

}

}

Output :

9
8
5
3
1

No Element found!