带child指针的单链表扁平化代码出现无限递归，求错误原因

问题重现 #

你有一个带child指针的多级链表，每个节点包含next（同级节点指针）和child（子链表头指针），需要扁平化为仅用next指针的单链表。示例输入如下：

1 --> 2 --> 3 --> 4 --> 5 --> 6
            |
            V 
            7 --> 8 --> 9 --> 10
                  |
                  V
                  11 --> 12

你提供的代码运行时触发了无限递归（或类似的栈溢出崩溃），以下是你的代码：

struct ListNode {
    int val;
    struct ListNode* next;
    struct ListNode* child;

    ListNode(int x) {
        val = x;
        next = NULL;
        child = NULL;
    }
};

ListNode* flatten(ListNode* head) {
    ListNode *temp = head, *r = NULL;
    while (temp) {
        if (temp->child) {
            r = temp->next;
            temp->next = flatten(temp->child);
        }
        if (!temp->next && r) {
            temp->next = r;
            r = NULL;
        }
        temp = temp->next;
    }
    return head;
}

错误原因分析 #

1. 未清空已处理的child指针 #

处理节点的child链表后，你没有将temp->child置为NULL。这会导致两种问题：

• 如果后续再次调用flatten函数，会重复处理同一个child链表，造成冗余计算；
• 若测试用例中存在环（比如某个节点的child指向父节点或自身），会直接触发无限递归。

2. 递归深度过大导致栈溢出（易被误认为无限递归） #

你的代码采用递归方式处理子链表，当多级链表的层级很深时，递归调用会持续占用栈空间，最终导致栈溢出，程序崩溃。这种情况的表现和无限递归类似，容易被混淆。

另外需要注意：你给出的预期输出是错误的，正确的扁平化结果应该是将子链表插入到当前节点和它的next节点之间，即：

1 -> 2 -> 3 -> 7 -> 8 -> 11 -> 12 -> 9 -> 10 -> 4 -> 5 -> 6

修复后的代码 #

递归版本（修复child指针问题） #

struct ListNode {
    int val;
    struct ListNode* next;
    struct ListNode* child;

    ListNode(int x) {
        val = x;
        next = NULL;
        child = NULL;
    }
};

ListNode* flatten(ListNode* head) {
    ListNode *temp = head, *r = NULL;
    while (temp) {
        if (temp->child) {
            r = temp->next;
            temp->next = flatten(temp->child);
            temp->child = NULL; // 关键：清空已处理的child指针
        }
        if (!temp->next && r) {
            temp->next = r;
            r = NULL;
        }
        temp = temp->next;
    }
    return head;
}

迭代版本（避免栈溢出） #

如果链表层级极深，建议使用迭代方式，通过栈保存待处理的节点：

ListNode* flatten(ListNode* head) {
    if (!head) return NULL;
    stack<ListNode*> stk;
    stk.push(head);
    ListNode* prev = NULL;

    while (!stk.empty()) {
        ListNode* curr = stk.top();
        stk.pop();

        if (prev) {
            prev->next = curr;
        }
        prev = curr;

        // 先压入next节点，再压入child节点，保证child先处理
        if (curr->next) {
            stk.push(curr->next);
        }
        if (curr->child) {
            stk.push(curr->child);
            curr->child = NULL; // 清空child指针
        }
    }
    return head;
}

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