Remove duplicate elements from unsorted linked list.

Consider example 12->11->3->4->11->1. In the given example it is required to remove the 11. So the list will look like : 12->3->4->1. This is one of my favorite question. As you see its a simple question but tricky because of various edge cases. Consider following scenarios:

  • list with single element 11
  • 11->23-34
  • 11->11->23->32
  • 23->34->45
  • 23->34->11->11
  • 1->23->11->34

The LinkedList for the example is singly. Here is how Node class looks like:

class Node {
	int value;
	protected Node next;
	
	public Node(int value) {
		this.value = value;
	}
	
	public int getValue() {
		return value;
	}
}

public class LinkedList {

	public Node removeNode(int value, Node curr) {
		Node start = curr;
		while(start.next != null) {
			if(start.next.value == value) {
				start.next = start.next.next;
			} else 
				start = start.next;
		}
		if( curr.value == value ) {
			curr = curr.next;
		}
		return curr;
	}	

	public static void main(String args[]) {
		Node start = new Node(1);
		LinkedList l = new LinkedList();
		l.addNode(1, start);
		l.addNode(1, start);
		l.addNode(5, start);
		l.addNode(1, start);
		l.print(start);
		start = l.removeNode(1, start);
		System.out.println(" ");
		l.print(start);
	}
}