C语言链表判断变位词问题：等长非变位词未正确返回0

问题背景 #

我有两个链表指针w1和w2，算法逻辑为：遍历w1的每个字符，在w2中查找该字符；找到则删除w2中对应字符，继续处理w1下一个字符。若所有字符都能找到返回1，否则返回0。当前代码在单词为变位词时可正常运行，但遇到长度相等但非变位词的单词时，无法按预期返回0。

原代码 #

int anagram(nodeptr w1,nodeptr w2){
    char key;
    int frog=1,n=0,r=0;
    nodeptr count1,count2,curr,prev=NULL;
    count1=w1;
    count2=w2;
    while(count1!=NULL){
        n++;
        count1=count1->next;
    }
    while(count2!=NULL){
        r++;
        count2=count2->next;
    }
    if(n!=r)
        frog=0;
    else {
        while(w1!=NULL) {
            key=w1->ch;
            prev=NULL;
            curr=w2;
            while(curr!=NULL&&key!=curr->ch){
                prev=curr;
                curr=curr->next;
            }
            if(key==curr->ch&&prev==NULL){
                w2=curr->next;
                free(curr);
            }
            else if(curr==NULL)
                frog=0;
            else{
                prev->next=curr->next;
                free(curr);
            }
      
            w1=w1->next;
        }
    }

    return frog;
}

问题根源 #

1. 空指针访问：当curr为NULL时，代码先执行if(key==curr->ch&&prev==NULL)，直接访问空指针的ch成员会触发未定义行为（程序崩溃或错误判断），导致永远走不到else if(curr==NULL)分支去设置frog=0。
2. 未提前终止循环：即使侥幸设置了frog=0，代码仍会继续遍历w1剩余字符，后续操作可能引发更多错误，也无执行必要。

修复方案 #

调整判断顺序避免空指针访问，同时在发现不匹配时立即终止循环：

修复后的代码 #

int anagram(nodeptr w1, nodeptr w2) {
    char key;
    int frog = 1;
    int n = 0, r = 0;
    nodeptr count1 = w1, count2 = w2;
    nodeptr curr, prev;

    // 统计链表长度
    while (count1 != NULL) {
        n++;
        count1 = count1->next;
    }
    while (count2 != NULL) {
        r++;
        count2 = count2->next;
    }

    // 长度不等直接返回非变位词
    if (n != r) {
        return 0;
    }

    // 遍历w1的每个字符，同时检查是否已确定非变位词
    while (w1 != NULL && frog) {
        key = w1->ch;
        prev = NULL;
        curr = w2;

        // 在w2中查找对应字符
        while (curr != NULL && key != curr->ch) {
            prev = curr;
            curr = curr->next;
        }

        // 找不到对应字符，标记为非变位词并终止循环
        if (curr == NULL) {
            frog = 0;
            break;
        }

        // 删除w2中找到的节点
        if (prev == NULL) {
            // 删除头节点
            w2 = curr->next;
        } else {
            // 删除中间节点
            prev->next = curr->next;
        }
        free(curr);

        w1 = w1->next;
    }

    return frog;
}

关键修复点 #

• 先判断curr是否为NULL，彻底避免空指针访问。
• 长度不等时直接返回0，减少冗余分支嵌套。
• 循环条件加入frog，一旦发现不匹配立即终止循环，避免无效操作。
• 简化删除节点逻辑，让代码更清晰易读。

内容的提问来源于stack exchange，提问作者learning to code