Q2_1.java

import java.util.*;

class Node {
	int content;
	Node next;

	Node(int x) {
		content = x;
		next = null;
	}
}

public class Q2_1 {

	public static void main(String args[]) {
		Node test1 = arrayToLinkedList(new int[] { 1 });
		Node test2 = arrayToLinkedList(new int[] { 1, 1 });
		Node test3 = arrayToLinkedList(new int[] { 1, 2, 3, 3, 5, 5 });

		remDup2(test1);
		remDup2(test2);
		remDup2(test3);

		System.out.println(compareLinkedList(test1,
				arrayToLinkedList(new int[] { 1 })));
		System.out.println(compareLinkedList(test2,
				arrayToLinkedList(new int[] { 1 })));
		System.out.println(compareLinkedList(test3,
				arrayToLinkedList(new int[] { 1, 2, 3, 5 })));

	}

	private static void remDup1(Node root) {
		HashSet<Integer> set = new HashSet<Integer>();
		Node previous = root;
		set.add(root.content);
		Node current = root.next;
		while (current != null) {
			if (set.contains(current.content)) {
				previous.next = current.next;
				current = previous.next;
			} else {
				set.add(current.content);
				previous = current;
				current = current.next;
			}
		}
	}

	private static void remDup2(Node root) {
		Node current = root;
		while (current != null) {
			Node beforeCheck = current;
			Node checkPoint = current.next;
			while (checkPoint != null) {
				if (checkPoint.content == current.content) {
					beforeCheck.next = checkPoint.next;

				} else {
					beforeCheck = checkPoint;
				}
				checkPoint = checkPoint.next;

			}
			current = current.next;
		}
	}

	private static Node arrayToLinkedList(int[] array) {
		Node head = new Node(array[0]);
		Node current = head;
		for (int i = 1; i < array.length; i++) {
			current.next = new Node(array[i]);
			current = current.next;
		}

		return head;
	}

	private static boolean compareLinkedList(Node root1, Node root2) {
		Node a = root1;
		Node b = root2;
		do {
			if (root1 == null && root2 == null)
				return true;
			if (root1 == null || root2 == null)
				return false;
			if (root1.content != root2.content)
				return false;
			root1 = root1.next;
			root2 = root2.next;
		} while (true);
	}
}