Delete duplicate value in linked list (Recursion in Java)

Question

I need to return the head of the linked list with all the duplicate elements deleted. I understand the logic of the problem, but I am getting confused in using recursion.

/*
Node is defined as 
class Node {
   int data;
   Node next;
}
*/

Node RemoveDuplicates(Node head) {
    if ((head == null) || (head.next == null))
        return head;
    else {
        RemoveDuplicates(head.next);
        if (head.data==head.next.data) head.next = head.next.next;  
    }
    return head;
}

If I call the function RemoveDuplicates(head.next) before the if condition; it works fine. However if I swap the order of the statements (rest everything is exactly the same)like:

if (head.data==head.next.data) head.next = head.next.next;
RemoveDuplicates(head.next);

the code is unable to correctly solve for a test case like '1->1->1->1'. The output I get in the latter case is '1->1'.

I would really like some suggestions on how I could understand recursion better.

A few details: - You don't need brackets around the two terms in the first if, as (== precedes ||)[docs.oracle.com/javase/tutorial/java/nutsandbolts/…. - By convention, methods in Java are not capitalized, i.e. it should be named removeDuplicates in this case. — Cedric Reichenbach
– Cedric Reichenbach, Commented Nov 23, 2016 at 8:22

Antony Dao · Accepted Answer · 2016-11-23 08:43:08Z

Firstly, your code does only solve if the list is in order, it cannot remove all duplicated node if data in random position, ex: 1, 2, 3, 1, 1, 2, 3

Secondly, for your concern, you can think it like below:

Case 1:

 RemoveDuplicates(head.next);
 if (head.data==head.next.data) head.next = head.next.next;

You check from element right before the end of the list, compare its data and the next data, if matched, replace the next node by the next next node. Then, jump to the previous node and repeat.

Case 2:

if (head.data==head.next.data) head.next = head.next.next; 
RemoveDuplicates(head.next);

You begin with the first node, check if it duplicate with the next node. If duplicated, bring the 3th node to replace the 2nd node. The, jump to the next node (now is the original 3rd node) to check if it duplicate to the next node. You see, you miss checking the 1st node and the original 3rd node.

I think you should try mode debug to understand deeply about this.

BTW, try to apply convention to your code. J Hope this help!

Cedric Reichenbach · Accepted Answer · 2016-11-23 08:38:10Z

The problem is that you "skip" some nodes in the latter case. Let's name the nodes in your example to see what's happening:

v
1 -> 1 -> 1 -> 1
a    b    c    d

v indicates the current reference of head in your method.

If you now do a check first, you compare a and b, then remove b:

v
1 -> 1 -> 1
a    c    d

Then you do a recursion step, which travels forward one node to c:

The problem is that you "skip" some nodes in the latter case. Let's name the nodes in your example to see what's happening:

v
1 -> 1 -> 1 -> 1
a    b    c    d

v indicates the current reference of head in your method.

If you now do a check first, you compare a and b, then remove b:

     v
1 -> 1 -> 1
a    c    d

And here's your problem. You never compared c to a value to its left, i.e. a/c or b/c.

This problem doesn't occur when switching the lines because that way you're walking the other way, i.e. you go through your list bottom-up (right to left) and only compare/delete to the right ("behind you" in walking direction).

Collectives™ on Stack Overflow

Delete duplicate value in linked list (Recursion in Java)

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related