9、链表与递归：递归遍历链表、递归反转链表、递归的优缺点

递归，这个词我当年学的时候，觉得它很玄乎。说白了，就是函数自己调用自己。你想想看，一个函数还没执行完，又调了一个自己，这栈帧一层层压下去，确实容易让人头晕。

但链表这东西，天生就适合递归。为啥？因为链表本身就是递归定义的——一个节点后面跟着另一个节点，直到 NULL。你顺着这个思路去想，递归遍历和递归反转，其实就顺理成章了。

9.1 递归遍历链表

先看最简单的：递归遍历。我记得刚入行那会儿，有个同事写链表遍历非要用递归，结果线上出了栈溢出。嗯，这里要注意，递归深度太深确实有风险。但理解递归遍历，是理解递归反转的基础。

递归遍历的核心思路：

• 如果当前节点是 NULL，就返回（递归终止条件）
• 否则，先处理当前节点，再递归处理下一个节点

代码长这样：

// 递归遍历链表（正序打印）
void traverse_recursive(Node* head) {
    if (head == NULL) {
        return;
    }
    printf("%d ", head->data);   // 先访问当前节点
    traverse_recursive(head->next); // 再递归下一个
}

如果你想逆序打印呢？很简单，把 printf 放到递归调用后面：

// 递归遍历链表（逆序打印）
void traverse_reverse_recursive(Node* head) {
    if (head == NULL) {
        return;
    }
    traverse_reverse_recursive(head->next); // 先递归到底
    printf("%d ", head->data);   // 回溯时打印
}

我在项目中遇到过一种场景：需要从尾到头输出日志链表。用迭代法得先反转再遍历，或者用栈。递归一行代码就搞定了——当然，前提是链表不太长。

9.2 递归反转链表

递归反转链表，是面试高频题。我第一次看到这个解法时，觉得这代码也太优雅了——但理解起来确实需要点功夫。

核心思想：

• 递归到最后一个节点，它就是新头
• 回溯时，把当前节点的 next 的 next 指向自己
• 再把当前节点的 next 置为 NULL

直接看代码：

// 递归反转链表，返回新头
Node* reverse_recursive(Node* head) {
    // 终止条件：空链表或只有一个节点
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    // 递归反转后面的链表
    Node* new_head = reverse_recursive(head->next);
    
    // 关键步骤：让下一个节点指向自己
    head->next->next = head;
    head->next = NULL;
    
    return new_head;
}

我画个图帮你理解这个过程：

这段代码的精髓在于：head->next->next = head。我第一次看这行时，愣了半天。说白了，就是让下一个节点反过来指向自己。你想想看，原来 1→2→3，递归到 3 返回后，在 2 这一层，head 是 2，head->next 是 3，那么 head->next->next = head 就是 3→2。

9.3 递归的优缺点

递归不是银弹。我用个表格给你对比一下：

对比项	递归	迭代
代码简洁性	非常简洁，逻辑清晰	相对冗长，需要手动维护指针
空间复杂度	O(n)，需要栈空间	O(1)，只使用几个指针
性能	函数调用有开销，可能较慢	通常更快
可读性	对熟悉递归的人很好	对所有人友好
栈溢出风险	链表太长时可能溢出	无此风险
调试难度	较难，调用栈深	容易，单步跟踪

我个人习惯是：链表长度可控（比如几百个节点以内）时，用递归写反转和遍历，代码漂亮。但如果是生产环境，链表可能很长，我建议用迭代。我曾经在一个嵌入式项目里，链表有上万节点，递归直接栈溢出，改成迭代后稳如老狗。

9.4 什么时候用递归？

给你几个判断标准：

• 链表长度已知且较小（比如 < 1000）—— 可以用
• 代码可读性优先（比如教学、原型）—— 推荐用
• 性能敏感（比如高频调用）—— 别用
• 栈空间紧张（比如单片机）—— 千万别用
• 需要逆序处理（比如从尾到头打印）—— 递归很自然

说白了，递归是一种思维工具。它让你用更少的代码表达更复杂的逻辑。但工具要用对地方，别拿着锤子看什么都像钉子。

---

公众号:蓝海资料掘金营，微信deep3321