递归释放循环单链表的正确基例选取及代码问题分析

问题原因分析 #

你现有实现漏释放最后一个节点的核心原因是：终止条件触发时，当前head正是链表中最后一个待释放的节点（其next指向原始头temp），你直接返回没有执行free逻辑，自然会残留这个节点。
另外你最初设想的if (head->next == head)终止基例只适用于单节点自环的场景，对于节点数大于1的循环单链表，遍历过程中永远不会出现某个节点的next指向自身的情况，该条件根本无法触发，会导致无限递归栈溢出。

仅传入单头指针的递归实现方案 #

对外仅暴露接受单个头指针的接口即可满足需求，终止基例统一设置为当前节点的next指针指向原始链表头，触发时先释放当前节点再返回，避免节点残留。

方案1：内部辅助函数实现（无静态变量，兼容性好） #

对外接口仅需传入头指针，内部递归时额外传入原始头参数，不依赖静态变量，多次调用不会互相干扰，也支持多线程场景：

typedef struct node
{
    int data;
    struct node *next;
} node;

// 内部辅助递归函数，不对外暴露
static node* destroy_helper(node *curr, node *origin_head)
{
    // 终止基例：遍历回到原始头，当前是最后一个待释放节点
    if (curr->next == origin_head) {
        free(curr);
        curr = NULL;
        return NULL;
    }
    destroy_helper(curr->next, origin_head);
    free(curr);
    curr = NULL;
    return NULL;
}

// 对外暴露的接口，仅需传入链表头一个参数
void destroy_circular_list(node *head)
{
    if (head == NULL) return;
    destroy_helper(head, head);
}

方案2：单参数递归函数实现（依赖静态变量） #

如果要求递归函数本身只能有一个参数，可以用静态变量存储原始头，注意用完重置静态变量避免后续调用出错：

node* recursive_destroyer(node *head)
{
    static node *origin_head = NULL;
    // 首次调用初始化原始头
    if (origin_head == NULL) {
        if (head == NULL) return NULL;
        origin_head = head;
    }
    // 终止基例：回到原始头，释放最后一个节点后重置静态变量
    if (head->next == origin_head) {
        free(head);
        head = NULL;
        origin_head = NULL;
        return NULL;
    }
    recursive_destroyer(head->next);
    free(head);
    head = NULL;
    return NULL;
}

注意：静态变量方案不是线程安全的，高并发场景下优先使用辅助函数方案。

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