C语言双向链表相邻重复节点移除：代码修正与正确方案

需求与原代码问题 #

需求是实现双向链表的相邻重复节点迭代移除功能：输入如google时，需经过google→ggle→le的迭代移除过程，最终输出le。原代码存在以下核心问题：

• 无法设置正确的循环终止条件，仅能处理一次重复移除，无法完成全量迭代处理
• 错误将待删除节点赋值给全局头指针head，导致最终输出空链表
• 删除节点的指针逻辑混乱，错误释放非待删除节点，存在内存访问风险与泄漏

原代码核心问题分析 #

• 迭代逻辑缺失：找到一次重复后直接break，无法触发后续迭代，无法处理删除后新产生的相邻重复
• 指针赋值错误：head=current;将待删除的重复节点末尾赋值给头指针，完全不符合逻辑；同时错误释放了需要保留的index和temp节点
• 边界处理遗漏：当current为头节点时，current->prev为NULL，直接访问会触发空指针崩溃；当current为尾节点时，访问current->next会触发非法内存访问
• 重复节点释放不完整：仅移动到重复段末尾就释放current，未释放中间所有重复节点，造成内存泄漏

修正后的完整代码 #

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

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

struct node *head, *tail = NULL;

void addNode(char data) {  
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = data;  
     
    if(head == NULL) {
        head = tail = newNode;
        head->prev = NULL;
        tail->next = NULL;
    } else {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
        tail->next = NULL;
    }  
}  

void remove_adjacent_duplicates() {
    int deleted;
    do {
        deleted = 0;
        struct node *current = head;
        while (current != NULL && current->next != NULL) {
            // 定位连续重复段起始位置
            if (current->data == current->next->data) {
                char dup_char = current->data;
                struct node *start = current;
                struct node *prev_node = current->prev;
                struct node *next_node;

                // 移动到连续重复段的末尾
                while (current != NULL && current->data == dup_char) {
                    current = current->next;
                }
                next_node = current;

                // 更新前后节点的指针连接
                if (prev_node != NULL) {
                    prev_node->next = next_node;
                } else {
                    // 删除的是头节点段，更新全局head
                    head = next_node;
                }
                if (next_node != NULL) {
                    next_node->prev = prev_node;
                } else {
                    // 删除的是尾节点段，更新全局tail
                    tail = prev_node;
                }

                // 释放所有重复节点内存
                struct node *temp = start;
                while (temp != current) {
                    struct node *next_temp = temp->next;
                    free(temp);
                    temp = next_temp;
                }

                deleted = 1;
                // 删除后回到前一个节点，检查是否产生新的相邻重复
                current = prev_node != NULL ? prev_node : head;
            } else {
                current = current->next;
            }
        }
    } while (deleted); // 直到一轮遍历无删除操作才终止迭代
}

void display() {  
    struct node *current = head;
    while(current != NULL) {  
        printf("%c<->", current->data);
        current = current->next;
    }  
    printf("NULL\n");  
}  

int main() {
    char s[100];
    int i;
   
    printf("Enter string: ");
    scanf("%s", s);
    
    int len = strlen(s);
    for(i = 0; i < len; i++) {
        addNode(s[i]);
    }
     
    printf("Doubly linked list: \n");  
    display();  
     
    remove_adjacent_duplicates();
    
    printf("Doubly linked list after removing adjacent duplicates: \n");  
    display();  
   
    return 0;
}

代码关键说明 #

• 迭代终止逻辑：使用do-while循环，只要某一轮遍历中删除了节点，就重新开始遍历，确保所有可能的相邻重复（包括删除后新产生的）都被处理
• 边界情况处理：分别处理删除头节点段、尾节点段的场景，正确更新全局head和tail指针，避免空指针访问
• 内存释放机制：遍历整个重复节点段，逐个释放内存，彻底避免内存泄漏
• 遍历重置机制：删除重复段后，将遍历起点重置到重复段的前一个节点，确保能检测到删除操作可能带来的新相邻重复

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