Removing Duplicate Node From A Linked List

This is actually a question from careercup.com. At first, I thought this question is easy, but later it seems it is harder than what I think. Sometimes, when you think something is easy, it is not that really easy, especially talking in computer programming languages: a world that is not real.

So. I already try to solve this last night, but I can’t. However, it seems that my energy is not wasted. After breaking for a while from ‘memorizing’ (I hate it) for software project management, I try to do the question again and I solved it!

So the question is:

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?

Note: the implementation here is using my own implementation of singly LinkedList.

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package cc_latihan;

/**
 *
 * @author adampbe
 */
public class RemoveDuplicateNode {

    public static void main (String[] args)
    {
    LinkedList ll = new LinkedList();
    ll.insert(0, new String("Impress"));
    ll.insert(1, new String("Design"));
    ll.insert(2, new String("Competition"));
    ll.insert(3, new String("Desire"));
    ll.insert(2, new String("Fear"));
    ll.insert(5, new String("Of"));
    ll.insert(3, new String("Failure"));

    System.out.println("The content of the linked list: ");
    System.out.println(ll);

    //remove duplicate
    System.out.println("Removing duplicate node based on its key...");
    Node currentNode = ll.root;
    Node nextNode = ll.root;
    for (; currentNode != null; currentNode = currentNode.next)
    {
        System.out.println("CURRENT NODE: " + currentNode);
        nextNode = currentNode.next;
        Node previousNode = currentNode;
        for (; nextNode != null; nextNode = nextNode.next)
        {
        System.out.println(" COMPARING WITH: " + nextNode);
        if (currentNode.key == nextNode.key)
        {
            System.out.println("  FOUND SAME!");
            System.out.println("  PREVIOUS NODE IS " + previousNode);
            previousNode.next = nextNode.next;
        }
        previousNode = previousNode.next;
        }
    }

    System.out.println("\nThe linked list content now: ");
    System.out.println(ll);

    }
}

The program when running:

run:
The content of the linked list: 
3: Failure
5: Of
2: Fear
3: Desire
2: Competition
1: Design
0: Impress

Removing duplicate node based on its key...
CURRENT NODE: 3: Failure
 COMPARING WITH: 5: Of
 COMPARING WITH: 2: Fear
 COMPARING WITH: 3: Desire
  FOUND SAME!
  PREVIOUS NODE IS 2: Fear
 COMPARING WITH: 2: Competition
 COMPARING WITH: 1: Design
 COMPARING WITH: 0: Impress
CURRENT NODE: 5: Of
 COMPARING WITH: 2: Fear
 COMPARING WITH: 2: Competition
 COMPARING WITH: 1: Design
 COMPARING WITH: 0: Impress
CURRENT NODE: 2: Fear
 COMPARING WITH: 2: Competition
  FOUND SAME!
  PREVIOUS NODE IS 2: Fear
 COMPARING WITH: 1: Design
 COMPARING WITH: 0: Impress
CURRENT NODE: 1: Design
 COMPARING WITH: 0: Impress
CURRENT NODE: 0: Impress

The linked list content now: 
3: Failure
5: Of
2: Fear
1: Design
0: Impress

BUILD SUCCESSFUL (total time: 0 seconds)

What I have learn are:

  1. Never think something is easy before you really sure you fluent with it. I never try this problem before, and thought it is an easy question and I even try to find harder question. The more advanced programmer always know more than us which one is required to get you to the next step 🙂
  2. To solve a data structure program, WE cannot depend 100% on our brain imagination. We have to write the implementation, and debug-test it. That’s how to figuring out how to solve the problem.
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