C语言递归实现单链表差集：相同ID节点如何跳过？

你的核心问题是当前代码无论节点是否匹配都会创建新节点，导致无法跳过匹配项。要实现跳过逻辑，只需在匹配时直接递归处理下一个节点，不执行新节点的创建和赋值即可，同时注意避免内存泄漏。

修改后的代码 #

struct singly* SetMinusRec(struct singly* shead1, struct singly* shead2){
    struct singly* s2end;

    s2end = shead2;

    if(shead1 == NULL){
        return NULL;
    }else{
        // 遍历降序的shead2，找到第一个id <= shead1->id的节点
        while(s2end != NULL && shead1->id < s2end->id){
            s2end = s2end->next;
        }
        
        // 检查当前shead1节点是否存在于shead2中
        if(s2end != NULL && shead1->id == s2end->id){
            // 匹配到目标节点，直接递归处理shead1的下一个节点，跳过当前节点
            return SetMinusRec(shead1->next, shead2);
        }else{
            // 未匹配到，创建新节点并加入结果链表
            struct singly* new_node = (struct singly*)malloc(sizeof(struct singly));
            new_node->id = shead1->id;
            // 递归处理后续节点，作为新节点的后继
            new_node->next = SetMinusRec(shead1->next, shead2);    
            return new_node;
        }
    }
}

关键逻辑说明 #

1. 匹配判断：循环结束后，s2end要么是NULL（说明shead1->id比shead2所有节点的id都小，不在shead2中），要么指向第一个id <= shead1->id的节点。此时若id相等，就说明该节点存在于shead2中，需要跳过。
2. 跳过操作：匹配时直接返回递归处理shead1下一个节点的结果，相当于直接推进shead1指针，不创建任何新节点，自然跳过当前匹配项。
3. 内存安全：仅在不匹配的分支分配内存，避免了原代码中匹配时malloc内存却未使用的泄漏问题。

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