Remove adjacent duplicates in linked list in C

Question

As the title mentioned, I have to remove adjacent duplicates in linked list such that if input is 'google', output should be 'le'. I'm supposed to code it in C. I've written 70% of the code, except that I don't know how to continuously loop till all adjacent duplicates are removed. I'm removing adjacent duplicates in remove_adjacent_duplicates() function, and since I don't know how to put terminating condition in loop, I've merely used if-else loop. But my code in remove_adjacent_duplicates() function might contain mistakes, so please rectify it if any and please give solution to looping till all adjacent duplicates are removed. Here's my code-

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node //node creation
{
  char data;
  struct node *next;
};

void remove_adjacent_duplicates(struct node** head_ref)
{
    struct node* current = *head_ref; 
    struct node* cnext = NULL; //the one next to current one
    int flag=0;
    
    cnext = current->next; //storing next
    //printf("%c %c %d\n",current->data,cnext->data,flag);
    
    if(cnext->data==current->data)
        {
            flag=1;
            while(cnext->data==current->data)
            {
                cnext=cnext->next;
            }
            current=cnext;
            cnext = current->next; //storing next

        }
        
    else
        {
            current=current->next;
            cnext = current->next; //storing next
            
        }
    //printf("%c %c %d\n",current->data,cnext->data,flag);
    if(flag) *head_ref = current;
    
}

void push(struct node** head_ref, char new_data)
{
    struct node* new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = new_data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}


void printList(struct node* head)
{
    if (head == NULL)
    {
        printf("NULL\n\n");
        return;
    }
    
    printf("%c->",head->data);
    printList(head->next);
}

int main()
{
    char s[100];
    int i;
    struct node* a = NULL;
    
    printf("Enter string: ");
    scanf("%s",s);
    
    for(i=strlen(s)-1;i>-1;i--){
        push(&a, s[i]); //last in first out, so in reverse g is last but first to come out
    }

    printf("\nConverting string to linked list: \n");
    printList(a);

    
    //printf("%c",current->data); prints first letter of a 
    remove_adjacent_duplicates(&a);
    
    printList(a);


    return 0;
}

Does `gooogle` (three o's) also result in `le`, or does it result in `gogle`? As in, should this function remove spans of duplicates or pairs? — Oka, Nov 06 '22 at 17:17
I suggest just making multiple passes through the list until you perform one in which no duplicates are removed. This implies that you will keep track on each pass of whether any dupes were removed during that pass. Alternatively, you could simply restart from the beginning each time you remove a duplicate pair. In that case, you would know you are done simply by reaching the end of the list. The latter is a bit simpler to implement, but often less efficient. — John Bollinger, Nov 06 '22 at 17:18
There are other alternatives too, some considerably more efficient, but I'm intuiting that your level of experience demands something simple. — John Bollinger, Nov 06 '22 at 17:25

score 2 · Accepted Answer · answered Nov 06 '22 at 17:25

You could use recursion. That way you can check whether before the recursive call or after the recursive call there is something to remove:

void remove_adjacent_duplicates(struct node** head_ref)
{
    struct node* current = *head_ref;
    if (current == NULL || current->next == NULL) return;
    int isEqual = current->data == current->next->data; 
    remove_adjacent_duplicates(&current->next);
    if (current->next != NULL && current->data == current->next->data) {
        // Duplicates! Remove pair
        *head_ref = current->next->next;
        free(current->next);
        free(current);
    } else if (isEqual) {
        // Continue ongoing removal
        *head_ref = current->next;
        free(current);
    }
}

Craig Estey · Answer 2 · 2022-11-07T17:33:33.923

A few issues ...

The first element of list (e.g. head) can never be a duplicate
The code leaks memory when removing a dup because it doesn't do free
The code only removes the first element.
The code uses next, cur, but not previous, so the algorithm needs refactoring.
Casting the return of malloc is bad. See: Do I cast the result of malloc?
scanf is problematic. %s can overrun the end of the array. Better to use (e.g.) %99s [or better yet: fgets].

Here is the refactored code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// node definition
struct node {
    char data;
    struct node *next;
};

void
remove_adjacent_duplicates(struct node **head_ref)
{
    struct node *prev = *head_ref;
    struct node *cur;
    struct node *next;

    // NOTE: first node can _never_ be a dup
    if (prev != NULL)
        cur = prev->next;
    else
        cur = NULL;

    for (;  cur != NULL;  cur = next) {
        // remember this in case we remove cur to prevent "use after free" bug
        // when advancing cur
        next = cur->next;

        // remove duplicate
        if (cur->data == prev->data) {
            prev->next = next;
            free(cur);
            continue;
        }

        // point to last non-dup node
        prev = cur;
    }
}

void
push(struct node **head_ref, char new_data)
{
// NOTE/BUG: casting the result of malloc is bad
#if 0
    struct node *new_node = (struct node *) malloc(sizeof(struct node));
#else
    struct node *new_node = malloc(sizeof(*new_node));
#endif

    new_node->data = new_data;
    new_node->next = *head_ref;

    *head_ref = new_node;
}

void
printList(struct node *head)
{
    if (head == NULL) {
        printf("NULL\n\n");
        return;
    }

    printf("%c->", head->data);
    printList(head->next);
}

int
main(void)
{
    char s[100];
    int i;
    struct node *a = NULL;

    printf("Enter string: ");
// NOTE/BUG: scanf is bad -- it can overrun the end of s
#if 0
    scanf("%s", s);
#else
    scanf("%99s", s);
#endif

    // last in first out, so in reverse g is last but first to come out
    for (i = strlen(s) - 1; i > -1; i--) {
        push(&a, s[i]);
    }

    printf("\nConverting string to linked list: \n");
    printList(a);

    // printf("%c",current->data); prints first letter of a
    remove_adjacent_duplicates(&a);

    printList(a);

    return 0;
}

In the above code, I've used cpp conditionals to denote old vs. new code:

#if 0
// old code
#else
// new code
#endif

#if 1
// new code
#endif

Note: this can be cleaned up by running the file through unifdef -k

UPDATE:

From the OP: "[ .. ] 'google', output should be 'le'.". Looks like both nodes are removed, and the effect compounds. – Oka

Yes, it's much more complex. But, here is a version that removes all duplicates. I had some trouble myself, so I left in the debugging code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if DEBUG
#define dbgprt(_fmt...) \
    printf(_fmt)
#else
#define dbgprt(_fmt...) \
    do { } while (0)
#endif

// node definition
struct node {
    char data;
#if DEBUG
    int seq;
#endif
    struct node *next;
};

#if DEBUG
int seq = 0;
#endif

void
remove_adjacent_duplicates(struct node **head_ref)
{
    struct node *prev = *head_ref;
    struct node *cur;
    struct node *next;

    // NOTE: first node can _never_ be a dup
    if (prev != NULL)
        cur = prev->next;
    else
        cur = NULL;

    for (;  cur != NULL;  cur = next) {
        // remember this in case we remove cur to prevent "use after free" bug
        // when advancing cur
        next = cur->next;

        // remove duplicate
        if (cur->data == prev->data) {
            prev->next = next;
            free(cur);
            continue;
        }

        // point to last non-dup node
        prev = cur;
    }
}

void
remove_all_duplicates(struct node **head_ref)
{
    struct node *oldhead = *head_ref;

    struct node *addprev = NULL;
    struct node *addnext;

    // loop through all candidate nodes
    for (struct node *addcur = oldhead;  addcur != NULL;  addcur = addnext) {
        int dupflg = 0;

        // start of search for duplicates to the right of the candidate
        struct node *prevdup = NULL;
        struct node *dupcur = addcur->next;

        // find all duplicates to the right [towards tail] of candidate node
        while (1) {
            // find first duplicate to the right of candidate [if one exists]
            struct node *dupnext = NULL;
            for (;  dupcur != NULL;  dupcur = dupnext) {
                dupnext = dupcur->next;
                if (dupcur->data == addcur->data) {
                    dupflg = 1;
                    break;
                }
                prevdup = dupcur;
            }

            // no more duplicates to the right of current candidate
            if (dupcur == NULL)
                break;

            // remove a duplicate on the right
            if (prevdup != NULL)
                prevdup->next = dupnext;
            else
                addcur->next = dupnext;
            free(dupcur);
        }

        addnext = addcur->next;

        // remove candidate because it's a dup
        if (dupflg) {
            if (addprev != NULL)
                addprev->next = addnext;
            else
                oldhead = addnext;
            free(addcur);
            continue;
        }

        // remember last valid non-dup node
        addprev = addcur;
    }

    *head_ref = oldhead;
}

void
push(struct node **head_ref, char new_data)
{
// NOTE/BUG: casting the result of malloc is bad
#if 0
    struct node *new_node = (struct node *) malloc(sizeof(struct node));
#else
    struct node *new_node = malloc(sizeof(*new_node));
#endif

    new_node->data = new_data;
#if DEBUG
    new_node->seq = seq++;
#endif
    new_node->next = *head_ref;

    *head_ref = new_node;
}

void
printList(struct node *head)
{
    if (head == NULL) {
        printf("NULL\n\n");
        return;
    }

#if DEBUG
    printf("%c%d->", head->data, head->seq);
#else
    printf("%c->", head->data);
#endif
    printList(head->next);
}

int
main(int argc,char **argv)
{
    char s[100];
    int opt_a = 0;
    int i;
    struct node *a = NULL;

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        char *cp = *argv;
        if (*cp != '-')
            break;

        switch (cp[1]) {
        case 'a':
            opt_a = ! opt_a;
            break;
        }
    }

    printf("Enter string: ");
// NOTE/BUG: scanf is bad -- it can overrun the end of s
#if 0
    scanf("%s", s);
#else
    fflush(stdout);
    if (fgets(s,sizeof(s),stdin) == NULL)
        s[0] = 0;
    s[strcspn(s,"\n")] = 0;
#endif

    // last in first out, so in reverse g is last but first to come out
    for (i = strlen(s) - 1; i > -1; i--)
        push(&a, s[i]);

    printf("\nConverting string to linked list: \n");
    printList(a);

    // printf("%c",current->data); prints first letter of a
    if (opt_a)
        remove_adjacent_duplicates(&a);
    else
        remove_all_duplicates(&a);

    printList(a);

    return 0;
}

UPDATE:

As for your code I can't understand it properly especially those # statements since I'm just an average coder in C with no advanced knowledge. – New

The # lines aren't really advanced coding. They are C preprocessor (i.e. cpp) directives, similar to #define, #ifdef, #ifndef, and #endif. See the compiler manpage and/or man cpp.

They include/eliminate code at compile time in a separate first stage of the compilation process (i.e. the cpp stage).

Otherwise, the code is well commented to explain the intent of what the code is doing.

Side note: When I was first learning to code, in addition to school assignments, I was looking at some complex OS kernel code [in assembly language]. I just kept going over it, sometimes adding my own comments, until I did understand it. I learned more by reading and understanding such code than I did from most assignments.

At the bottom of my answer: What is the error in this code that checks if the linklist is a palindrome or not? is a list of resources I recommend.

Here is a cleaned up version of the my code above that eliminates the conditional cpp directives:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// node definition
struct node {
    char data;
    struct node *next;
};

void
remove_adjacent_duplicates(struct node **head_ref)
{
    struct node *prev = *head_ref;
    struct node *cur;
    struct node *next;

    // NOTE: first node can _never_ be a dup
    if (prev != NULL)
        cur = prev->next;
    else
        cur = NULL;

    for (;  cur != NULL;  cur = next) {
        // remember this in case we remove cur to prevent "use after free" bug
        // when advancing cur
        next = cur->next;

        // remove duplicate
        if (cur->data == prev->data) {
            prev->next = next;
            free(cur);
            continue;
        }

        // point to last non-dup node
        prev = cur;
    }
}

void
remove_all_duplicates(struct node **head_ref)
{
    struct node *oldhead = *head_ref;

    struct node *addprev = NULL;
    struct node *addnext;

    // loop through all candidate nodes
    for (struct node *addcur = oldhead;  addcur != NULL;  addcur = addnext) {
        int dupflg = 0;

        // start of search for duplicates to the right of the candidate
        struct node *prevdup = NULL;
        struct node *dupcur = addcur->next;

        // find all duplicates to the right [towards tail] of candidate node
        while (1) {
            // find first duplicate to the right of candidate [if one exists]
            struct node *dupnext = NULL;
            for (;  dupcur != NULL;  dupcur = dupnext) {
                dupnext = dupcur->next;
                if (dupcur->data == addcur->data) {
                    dupflg = 1;
                    break;
                }
                prevdup = dupcur;
            }

            // no more duplicates to the right of current candidate
            if (dupcur == NULL)
                break;

            // remove a duplicate on the right
            if (prevdup != NULL)
                prevdup->next = dupnext;
            else
                addcur->next = dupnext;
            free(dupcur);
        }

        addnext = addcur->next;

        // remove candidate because it's a dup
        if (dupflg) {
            if (addprev != NULL)
                addprev->next = addnext;
            else
                oldhead = addnext;
            free(addcur);
            continue;
        }

        // remember last valid non-dup node
        addprev = addcur;
    }

    *head_ref = oldhead;
}

void
push(struct node **head_ref, char new_data)
{
    struct node *new_node = malloc(sizeof(*new_node));

    new_node->data = new_data;
    new_node->next = *head_ref;

    *head_ref = new_node;
}

void
printList(struct node *head)
{
    if (head == NULL) {
        printf("NULL\n\n");
        return;
    }

    printf("%c->", head->data);
    printList(head->next);
}

int
main(int argc,char **argv)
{
    char s[100];
    int opt_a = 0;
    int i;
    struct node *a = NULL;

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        char *cp = *argv;
        if (*cp != '-')
            break;

        switch (cp[1]) {
        case 'a':
            opt_a = ! opt_a;
            break;
        }
    }

    printf("Enter string: ");
    fflush(stdout);
    if (fgets(s,sizeof(s),stdin) == NULL)
        s[0] = 0;
    s[strcspn(s,"\n")] = 0;

    // last in first out, so in reverse g is last but first to come out
    for (i = strlen(s) - 1; i > -1; i--)
        push(&a, s[i]);

    printf("\nConverting string to linked list: \n");
    printList(a);

    // printf("%c",current->data); prints first letter of a
    if (opt_a)
        remove_adjacent_duplicates(&a);
    else
        remove_all_duplicates(&a);

    printList(a);

    return 0;
}

This prints `g->o->g->l->e->NULL`. AFAICT, the expectation was `l->e->NULL`? Aside: beyond the algorithm, `scanf("%s", s);` remains as dangerous as `gets`. — Oka, Nov 06 '22 at 17:31
@Oka Ack on `scanf`. But, the question says _adjacent_ duplicates, so `oo` -> `o` but the non-adjacent `g` should remain. Here, this is O(n). But, without sorting, removal of all dups would be O(n^2) — Craig Estey, Nov 06 '22 at 17:45
From the OP: *"[ .. ] 'google', output should be 'le'."*. Looks like both nodes are removed, and the effect compounds. — Oka, Nov 06 '22 at 17:48
@Oka Okay, to be complete, I've added a version that eliminates all duplicates [_without_ sorting] per the `google` --> `le` criterion. — Craig Estey, Nov 06 '22 at 19:35
Thank you very much for your help @trincot ! Also, it seems I didn't clearly mention what removal of adjacent duplicates meant. Suppose the string is ggooljkhhkj. Then the operation is like this--> ggooljkhhkj-->ooljkhhkj-->ljkhhkj-->ljkkj-->ljj-->l . So final output should be l — New, Nov 07 '22 at 12:17
@New My latest version _does_ do: `ggooljkhhkj` --> `l`. As to the wording, originally I saw _adjacent_ but didn't see the `google` --> `le` example [which is clear enough]. Instead of "remove _adjacent_ duplicates", I would have said "remove _all_ duplicates". Or, "reduce the list to those _unique_ characters that occur only once" — Craig Estey, Nov 07 '22 at 14:43
@CraigEstey I was just explaining to others who got confused. As for your code I can't understand it properly especially those # statements since I'm just an average coder in C with no advanced knowledge. — New, Nov 07 '22 at 17:00
@New I've updated my answer with some additional explanation and a cleaned up example — Craig Estey, Nov 07 '22 at 17:35

Remove adjacent duplicates in linked list in C

2 Answers2

Linked