已实现链表镜像递归C代码 求解析逻辑及指定递归调用的执行流程

核心本质 #

这个mirror函数是典型的前序递归处理正向节点 + 后序递归处理反向节点的组合实现，你困惑的new->next = mirror(head->next)这行并非本身完成所有节点插入操作，而是递归调用的栈切换入口，依靠函数调用栈暂存每一层的执行上下文，最终拼出完整的镜像链表。

单帧执行顺序拆解 #

每一次调用mirror函数，单一层级的固定执行流如下：

• 边界判断：若传入的head为NULL，直接返回NULL作为递归终止点
• 前序操作：在当前层持有的局部链表new末尾，插入当前head节点存储的data值——这一步在递归深入执行前完成，负责搭正向链表的骨架
• 递归触发：将当前层new的next指针，赋值为mirror(head->next)的返回值——执行到这行时，当前层会立刻暂停，把所有局部变量的上下文压入调用栈，转而去处理原链表的下一个节点
• 后序操作：等递归调用的返回值拿到（也就是所有深层节点处理完成）后，在当前层的new链表末尾，再插入一次当前head节点存储的data值——这一步在递归逐层返回后完成，负责补全镜像的反向部分
• 返回当前层new的头指针，传给上一层的调用者

极简示例全流程走查 #

以输入链表1->2->3->NULL为例，完整执行栈流转过程如下：

压栈阶段（从原链表头往尾走，触发递归深入）：

1. 第1层调用：head指向data=1的节点
   • 边界判断通过，执行前序PushEnd：此时层内new为1->NULL
   • 触发递归：暂停当前层所有执行，压栈处理head->next（也就是data=2的节点），栈中暂存当前new的地址、data=1的值
2. 第2层调用：head指向data=2的节点
   • 边界判断通过，执行前序PushEnd：此时层内new为2->NULL
   • 触发递归：暂停当前层，压栈处理head->next（data=3的节点），栈中暂存当前new的地址、data=2的值
3. 第3层调用：head指向data=3的节点
   • 边界判断通过，执行前序PushEnd：此时层内new为3->NULL
   • 触发递归：暂停当前层，压栈处理head->next（NULL），栈中暂存当前new的地址、data=3的值
4. 第4层调用：head为NULL
   • 触发边界判断，直接返回NULL，递归终止，开始逐层弹栈恢复执行

弹栈阶段（从原链表尾往头回，完成节点拼接和反向插入）：

1. 回到第3层暂停点：拿到递归返回的NULL，将层内new的next赋值为NULL，此时new为3->NULL
   • 执行后序PushEnd：在链表末尾插入data=3，此时new更新为3->3->NULL
   • 返回new的头指针给第2层
2. 回到第2层暂停点：拿到第3层返回的3->3->NULL的头地址，将层内new的next接到这个地址上，此时new为2->3->3->NULL
   • 执行后序PushEnd：在链表末尾插入data=2，此时new更新为2->3->3->2->NULL
   • 返回new的头指针给第1层
3. 回到第1层暂停点：拿到第2层返回的2->3->3->2->NULL的头地址，将层内new的next接到这个地址上，此时new为1->2->3->3->2->NULL
   • 执行后序PushEnd：在链表末尾插入data=1，此时new更新为完整的镜像链表1->2->3->3->2->1->NULL
   • 将这个最终链表的头指针返回给主调用方

关键认知澄清 #

你对那行递归调用的困惑，本质是混淆了普通顺序执行和递归的执行顺序：

• 那行new->next = mirror(head->next)本身不执行任何节点插入逻辑，只负责触发递归、保存当前层的暂停状态
• 整个插入过程是分层完成的：压栈阶段顺着原链表方向插正向节点，弹栈阶段逆着原链表方向插反向节点
• 每一层只负责完成两个连接动作：把自己存的正向节点，和下一层返回的完整子镜像链通过next指针对齐；再把自己存的反向节点，接到整个子镜像链的末尾
• 原链表的每个节点在压栈阶段只被访问一次，完全符合题目的访问要求

实现的小局限 #

这个写法虽然满足“原链表每个节点仅访问一次”的要求，但因为PushEnd每次都需要遍历到新链表的尾部才能插入，整体时间复杂度是O(n²)，空间复杂度是O(n)（递归栈深度等于原链表长度）。如果要优化到O(n)时间，可以在递归的时候直接记录新链表的尾指针，避免每次遍历找尾。

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