C语言链表相邻重复元素删除：代码修正与循环实现方案

问题描述 #

需求：用C语言实现链表中相邻重复元素的删除功能，输入示例"google"对应的输出应为"le"。
现有问题：已完成约70%代码，但无法实现循环处理直至所有相邻重复元素被删除，且remove_adjacent_duplicates()函数存在错误，请求修正该函数并提供循环终止的解决方案。
现有代码如下：

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

修正后的完整代码 #

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

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

void remove_adjacent_duplicates(struct node** head_ref)
{
    // 处理空链表或只有一个节点的边界情况
    if (*head_ref == NULL || (*head_ref)->next == NULL)
        return;

    // 创建哑节点，简化头部节点的删除操作
    struct node* dummy = (struct node*)malloc(sizeof(struct node));
    dummy->next = *head_ref;
    struct node* prev = dummy;
    int changed;

    // 循环遍历直到没有重复元素被删除
    do {
        changed = 0;
        struct node* current = prev->next;
        while (current != NULL && current->next != NULL) {
            if (current->data == current->next->data) {
                changed = 1;
                char dup_val = current->data;
                // 一次性删除所有连续重复的节点
                while (current != NULL && current->data == dup_val) {
                    struct node* temp = current;
                    current = current->next;
                    free(temp); // 释放内存，避免泄漏
                }
                prev->next = current;
            } else {
                // 无重复时移动指针继续遍历
                prev = current;
                current = current->next;
            }
        }
        prev = dummy; // 重置前驱指针，重新从头遍历
    } while (changed);

    // 更新头节点并释放哑节点
    *head_ref = dummy->next;
    free(dummy);
}

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 >= 0; i--){
        push(&a, s[i]);
    }

    printf("\nOriginal linked list: \n");
    printList(a);

    remove_adjacent_duplicates(&a);

    printf("After removing adjacent duplicates: \n");
    printList(a);

    return 0;
}

关键修改说明 #

• 哑节点（Dummy Node）：创建哑节点避免单独处理头节点被删除的边界情况，简化链表操作逻辑。
• 循环遍历机制：通过changed标记控制循环，只要某次遍历删除了重复元素，就重新从头遍历，确保删除重复后新出现的相邻重复也被处理（比如"google"删除"oo"后，前后的"g"变为相邻，需要再次遍历删除）。
• 内存释放：删除节点时调用free()释放内存，避免内存泄漏问题。
• 完整重复删除：遇到重复元素时，一次性删除所有连续的重复节点，而非仅单个节点。
• 边界处理：增加对空链表或单节点链表的判断，防止空指针访问错误。

内容的提问来源于stack exchange，提问作者New