尾递归如何优化LeetCode逆序链表相加递归代码？复杂度解析

问题背景 #

我在刷LeetCode的两逆序链表相加题（要求结果链表也得是逆序），现在写的递归代码只超过了24%的提交。想改成尾递归形式搞懂它的原理，主要想弄明白两个问题：

1. 尾递归到底是怎么优化时空复杂度的？
2. 是不是把局部变量改成参数传递就行？

原递归代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode digit = null;

        int sum = l1.val + l2.val;
        int carry = sum / 10;
        int place = sum % 10;

        if (l1.next != null && l2.next != null) {
            l1.next.val += carry;
            digit = AddTwoNumbers(l1.next, l2.next);
        } else if (l1.next != null) 
            digit = AddTwoNumbers(l1.next, new ListNode(carry, null));
        else if (l2.next != null) 
            digit = AddTwoNumbers(new ListNode(carry, null), l2.next);
        else if (carry > 0)
            return new ListNode(place, new ListNode(carry, digit)); 

        return new ListNode(place, digit);
    }

尾递归的优化逻辑 #

1. 尾递归对时空复杂度的改善 #

普通递归每调用一次，都会在调用栈里存储当前函数的局部变量、返回地址等信息，递归深度等于链表长度，空间复杂度为O(n)。而尾递归是指递归调用是函数最后执行的操作——这种情况下，编译器可以直接复用当前栈帧，不用保留旧栈帧，空间复杂度能降到O(1)（前提是编译器支持尾递归优化，比如C#在Release模式下会做这个优化）。

时间复杂度上，尾递归和普通递归都是O(n)，但尾递归减少了栈帧创建、销毁的额外开销，实际运行效率会更高。

2. 改造尾递归不止是移变量到参数 #

核心是要把后续需要的状态（比如当前的进位、已经建好的结果链表尾部）作为参数传递，并且让递归调用成为函数的最后一步——不能像原代码那样，递归返回后还要创建新节点拼接，这种情况编译器没法做优化。

改造后的尾递归实现 #

可以新增一个辅助的尾递归函数，把进位、当前结果链表的尾部节点作为参数传进去，代码示例：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
    // 用哑节点处理边界，不用纠结头节点的创建逻辑
    ListNode dummy = new ListNode(0);
    // 初始进位为0，当前结果节点指向哑节点
    TailRecursiveAdd(l1, l2, 0, dummy);
    return dummy.next;
}

// 尾递归辅助函数：最后一步就是调用自身，无额外后续操作
private void TailRecursiveAdd(ListNode l1, ListNode l2, int carry, ListNode currentResult) {
    // 终止条件：两个链表都遍历完，且没有剩余进位
    if (l1 == null && l2 == null && carry == 0) {
        return;
    }

    // 计算当前位的总和
    int sum = carry;
    sum += l1 != null ? l1.val : 0;
    sum += l2 != null ? l2.val : 0;

    int currentVal = sum % 10;
    int newCarry = sum / 10;

    // 将当前节点添加到结果链表尾部
    currentResult.next = new ListNode(currentVal);

    // 递归处理下一位，传递更新后的参数
    TailRecursiveAdd(
        l1?.next, 
        l2?.next, 
        newCarry, 
        currentResult.next
    );
}

改造说明 #

• 新增dummy哑节点，避免处理头节点为空的复杂边界情况。
• TailRecursiveAdd的最后一步就是调用自身，没有额外的节点拼接操作，符合尾递归定义，编译器可以优化栈帧。
• 把进位、结果链表的当前尾部作为参数传递，每次递归更新这些状态。
• 空间复杂度从原代码的O(n)降到O(1)（Release模式下），运行效率会明显提升。

原代码为啥不是尾递归？ #

原代码中，递归调用AddTwoNumbers之后，还要执行return new ListNode(place, digit)——也就是递归返回后还要创建新节点并拼接，这就不符合尾递归的要求。因为递归调用不是函数的最后一步操作，编译器无法复用栈帧，所以空间复杂度还是O(n)，而且每次递归都要等待上层返回再拼接节点，效率自然偏低。

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