What's wrong with my code to delete duplicate-value nodes from a sorted linked list?

1
votes

Problem statement: Delete duplicate-value nodes from a sorted linked list

Input Format:

You have to complete the Node* RemoveDuplicates(Node* head) method which takes one argument - the head of the sorted linked list. You should NOT read any input from stdin/console.

Output Format:

Delete as few nodes as possible to ensure that no two nodes have the same data. Adjust the next pointers to ensure that the remaining nodes form a single sorted linked list. Then return the head of the sorted updated linked list.

My Code:

Node RemoveDuplicates(Node head) {   
    Node n  = head;
    while(n.next!=null){
        Node test = n.next;
        while(n.data==test.data){
            if(test.next!=null){
                n.next = test.next;
                test = n.next;
            }
            else{
                n.next = null;
            }
        }
        if((n.next!=null)){
            n = n.next;
        }
    }
    return head;
}

When tested, it runs perfectly except when the last node's value is equal to previous node's value. I couldn't find the mistake in my code.

Test results:

The first int is the number of test cases and second int is the number of nodes in the list.

Problem taken from HackerRank.

3
javadata-structureslinked-list

3 Answers

1
votes

You are just not finishing the loop.

Lets debug what happens when in this case,

n.data = 15;
n.next = test;
test.data = 15;
test.next == null;

You inner while loop will return true, and you will enter the else condition.

There you are setting n.next = null and continuing with the loop. But the loops condition remains the same... So it will go into an infinite loop.

Fix: Just break out of the loop after setting n.next = null.

else{
    n.next = null;
    break;
}
0
votes

change your inner while loop to 

    while(n.next!=null && n.data==test.data){
       .....
    }

when your last two nodes are equal, you are making n.next=null; but you not checking whether next is null or not, just checking n.data && test.data, which is causing the problem.

-1
votes

The code is also overly complicated. Try this (couldn't test right now):

Node RemoveDuplicates(Node head) {   
    if (head == null) return null;
    Node prev  = head;
    Node curr = head.next;
    while(curr != null){
        if (prev.data == curr.data)
            prev.next = curr.next;
         else
             prev = prev.next;
         curr = curr.next;
    }
    return head;
}