Remove duplicates from an unsorted Linked List

Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?

My initial thoughts:
Because we don’t want to use any large space, we can keep record of two iterators to go through the entire list and check to see if there are duplicates. So that’s an O(n^2) time complexity and O(1) space complexity solution.

My initial codes (solution):

	public static void removeDuplicates(LLNode<Integer> head) {
		LLNode<Integer> left = head;

		while (left.getNext() != null) {
			LLNode<Integer> previous = left;
			LLNode<Integer> right = left.getNext();
			do {
				if (right.getData() == left.getData()) {
					previous.setNext(right.getNext());
					right.setNext(null);
					right = previous.getNext();
				} else {
					previous = right;
					right = right.getNext();
				}
			} while (right != null);
			left = left.getNext();
		}

	}

Comments after running:

  • It works fine for multiple elements, multiple duplicates, etc.
  • Failed for 1 -> 1.

Correction:


	public static void removeDuplicates(LLNode<Integer> head) {
		LLNode<Integer> left = head;

		while (left != null) {
			LLNode<Integer> previous = left;
			LLNode<Integer> right = left.getNext();
			while (right != null) {
				if (right.getData() == left.getData()) {
					previous.setNext(right.getNext());
					right.setNext(null);
					right = previous.getNext();
				} else {
					previous = right;
					right = right.getNext();
				}
			}
			left = left.getNext();
		}

	}

Solution:

	public static void deleteDups2(LLNode<Integer> head) {
		if (head == null)
			return;
		LLNode<Integer> previous = head;
		LLNode<Integer> current = previous.getNext();
		while (current != null) {
			LLNode<Integer> runner = head;
			while (runner != current) { // Check for earlier dups
				if (runner.getData() == current.getData()) {
					LLNode<Integer> tmp = current.getNext(); // remove current
					previous.setNext(tmp);
					current = tmp; // update current to next node
					break; // all other dups have already been removed
				}
				runner = runner.getNext();
			}
			if (runner == current) { // current not updated - update now
				previous = current;
				current = current.getNext();
			}
		}
	}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: