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

CodePudding user response：

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

CodePudding user response：

A few issues ...

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