LeetCode两数相加问题：链表相加代码陷入无限循环求解

题目描述 #

给定两个非空链表，表示两个非负整数。数字以逆序存储，每个节点包含一个数字。将两数相加并以链表形式返回和。
可以假设除了数字0本身外，两个数都没有前导零。

问题重现 #

我实现的代码陷入无限循环，代码如下：

private static Node addTwoNumbers(Node l1, Node l2) {
    if (l1 == null && l2 == null)
        return l1;
    if (l1 == null) {
        l2.next = addTwoNumbers(l2, l1);
        return l2;
    }
    if (l2 == null) {
        if (l1.data > 9) {
            if (l1.next != null) {
                l1.next.data = l1.next.data + 1;
            } else
                l1.next = new addLinkedList().new Node(1);

            l1.data = (l1.data) % 10;
        }
        l1.next = addTwoNumbers(l1.next, l2);
        return l1;

    }

    if (l1.data + l2.data > 9) {
        l1.data = (l1.data + l2.data) % 10;
        if (l1.next != null) {
            l1.next.data = l1.next.data + 1;
        } else
            l1.next = new addLinkedList().new Node(1);

    } else {
        l1.data = l1.data + l2.data;

    }
    l1.next = addTwoNumbers(l1.next, l2.next);
    return l1;

}

输入：L1=0->null L2=5->9->null
预期输出：5->9->null
实际输出：5->9->9->9->...（无限循环）

修改第5行代码为l2.next = addTwoNumbers(l2.next, l1);后可得到正确输出，下面分析原代码无限循环的根本原因。

无限循环的根源分析 #

针对给定输入，我们逐步追踪递归执行流程：

1. 初始调用：addTwoNumbers(l1=0->null, l2=5->9->null)

   • 两链表均非空，计算0+5=5，将l1.data改为5。
   • 递归调用addTwoNumbers(l1.next=null, l2.next=9->null)。

2. 递归调用1：addTwoNumbers(null, 9->null)

   • 触发l1 == null分支，执行l2.next = addTwoNumbers(l2=9->null, l1=null)，随后返回l2。

3. 递归调用2：addTwoNumbers(9->null, null)

   • 触发l2 == null分支，l1.data=9不大于9，无需处理进位。
   • 递归调用addTwoNumbers(9.next=null, null)，返回null。
   • 将9.next设为null，返回节点9本身。

4. 回到递归调用1：

   • 执行l2.next = 递归调用2的返回值，也就是把节点9的next指向它自己，形成了自引用的循环链表。

5. 回到初始调用：

   • 将l1.next设为这个循环的节点9，最终链表变为5->9->9->9->...，遍历会无限循环。

为什么修改后能解决问题 #

修改后的代码l2.next = addTwoNumbers(l2.next, l1)，是递归调用addTwoNumbers(9.next=null, null)，该调用返回null，因此l2.next被设为null，不会形成自引用循环，最终得到正确的5->9->null链表。

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