C语言提取两链表独有元素存入第三链表时全部元素被插入问题

问题根因 #

• 遍历链表1的外层循环中，仅首次进入内层循环时aux_path2指向链表2头节点，第一次内层循环执行完aux_path2就变为NULL，后续所有外层循环的内层判断都不会执行，exist始终为0，导致链表1的所有节点都被插入结果链表
• 同理，遍历链表2的外层循环中，每轮内层循环执行完aux_path1就变为NULL，后续外层循环的内层判断不会执行，exist始终为0，导致链表2的所有节点也都被插入结果链表

修复方案 #

将内层循环的遍历指针重置逻辑放到每轮外层循环内，不要只在函数开头赋值一次。同时建议把辅助指针改为局部变量，避免全局变量污染引发其他异常，也可在找到重复元素时提前跳出内层循环减少不必要的遍历，修复后代码如下：

void path_union(lp head_list_1, lp head_list_2) 
{
    // 辅助指针改为局部变量，避免全局变量冲突
    lp aux_path_1, aux_path_2;
    int exist;

    // 筛选链表1独有的节点
    aux_path_1 = head_list_1;
    while (aux_path_1 != NULL)
    {     
        exist = 0;
        // 每轮外层循环都重置aux_path2为链表2头节点
        aux_path_2 = head_list_2;
        while (aux_path_2 != NULL)
        {
            if (aux_path_1->row == aux_path_2->row && aux_path_1->column == aux_path_2->column)
            {
                exist=1;
                // 找到重复提前退出，减少遍历开销
                break;
            }
            aux_path_2 = aux_path_2->next;
        }
        if (exist == 0)
        {
            insert_union(head_list_3, aux_path_1->row, aux_path_1->column);
        } 
        aux_path_1 = aux_path_1->next;
    }

    // 筛选链表2独有的节点
    aux_path_2 = head_list_2;
    while (aux_path_2 != NULL)
    {     
        exist = 0;
        // 每轮外层循环都重置aux_path1为链表1头节点
        aux_path_1 = head_list_1;
        while (aux_path_1 != NULL)
        {
            if (aux_path_2->row == aux_path_1->row && aux_path_2->column == aux_path_1->column)
            {
                exist = 1;
                break;
            }
            aux_path_1 = aux_path_1->next;
        }
        if (exist == 0)
        {
            insert_union(head_list_3, aux_path_2->row, aux_path_2->column);
        }
        aux_path_2 = aux_path_2->next;
    }  
}

注意事项 #

调用path_union前请确保head_list_3已经完成初始化，若使用哑结点实现，初始状态下head_list_3的next指针需设为NULL，避免插入操作出现野指针异常。

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