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

Question

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.

Codebender · Accepted Answer · 2015-07-10 10:59:51Z

1

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;
}

answered Jul 10, 2015 at 10:59

Codebender

14.5k7 gold badges51 silver badges87 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Charan Over a year ago

Yes, that fixed it. I may have overlooked the else condition. Thank you so much.

Karthik · Accepted Answer · 2015-07-10 10:59:47Z

0

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.

answered Jul 10, 2015 at 10:59

Karthik

5,0387 gold badges39 silver badges67 bronze badges

Comments

Roberto Attias · Accepted Answer · 2015-07-10 17:11:14Z

-1

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;
}

answered Jul 10, 2015 at 17:11

Roberto Attias

1,9031 gold badge12 silver badges21 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related