CODEWITHSUNDEEP
crecursionlinked-list
Kon
Kon

Reputation: 25

Recursively removing the duplicate elements in a linked list

I was trying to remove the duplicate element in a sorted linked list using recursion concept.

I wanna see how to remove the elements in a sorted linked list. I made a code in which if head->data == head->next->data than head->next should be freed until we get the different element. Now I have made so many changes I am confused how I am supposed to do it. It is deleting every value that is duplicate and only leaving the one that was only appeared in the entire code only once.

Please also tell me why this code is doing this and also what can wrong with code and if any optimal way possible to do the same thing.

(I am only providing the deleteduplicate function if there is a need to provide the whole code like print the list or insert in the list I will edit it if told).

Thanks.

Node *deleteDuplicates(Node *head) { 
    if (head == NULL || head->next == NULL) {
        return head;
    }
    if (head->data == head->next->data) {
        struct Node *x = head->next;
        head->next = head->next->next;
        free(x);
        return deleteDuplicates(head);
    } else
        return deleteDuplicates(head->next);
}

Input: 11 11 11 13 13 20

Output: 20

Expected output: 11 13 20

Upvotes: 2

Views: 594

Answers (2)

chqrlie
chqrlie

Reputation: 144715

There is no need for recursion in this function. Just iterate in a loop either removing the next element or skipping to the next element:

Node *deleteDuplicates(Node *head) {
    if (head != NULL) {
        Node *p = head;
        while (p->next) {
            if (p->next->data == p->data) {
                Node *x = p->next;
                p->next = x->next;
                free(x);
            } else {
                p = p->next;
            }
        }
    }
    return head;
}

You could fix your recursive function, but it should be modified to not return the head node as this prevents tail recursion, therefore requiring a potentially huge amount of stack space. A sufficiently long list would cause a Stack overflow.

Here is a modified recursive function:

void deleteDuplicates(Node *head) { 
    if (head != NULL && head->next != NULL) {
        if (head->data == head->next->data) {
            struct Node *x = head->next;
            head->next = x->next;
            free(x);
            deleteDuplicates(head);
        } else {
            deleteDuplicates(head->next);
        }
    }
}

The problem in your code is you store the return value of deleteDuplicates into your head pointer, but the function returns the pointer to the last node in the list, not the head node.

Upvotes: 1

Gaurav Sehgal
Gaurav Sehgal

Reputation: 7542

It is deleting every value that is duplicate and only leaving the one value that was only appeared in the entire code only once.

No. It is deleting only duplicate values but you always return pointer to the last node.

if(head==NULL ||head->next==NULL){
   return head;
}

You don't need to return the new head, since only duplicates are going to be removed, there is no way head is going to change.

Upvotes: 2

Related Questions