在 Java 中使用递归将链表表示的两个数字相加

Question

PS：有多个关于添加两个由链表表示的数字的帖子，但没有一个谈论递归解决方案。因此，请不要标记为重复的反对票。

问。您将获得两个非空链表，代表两个 非负整数。数字以相反的顺序存储，每个数字 的节点包含一位数字。将两个数字相加并返回 它作为链表。

您可以假设这两个数字不包含任何前导零，除了 数字 0 本身。

我的尝试

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode l3 = new ListNode(0);
recursiveAdd(l1, l2, l3, 0);
return l3;
}
private void recursiveAdd(ListNode l1, ListNode l2, ListNode l3, int carryOver){
if(l1 != null || l2!= null){
l3.val = (l1==null?0:l1.val + (l2==null?0:l2.val) + carryOver)%10;
l3.next = new ListNode(0);
int carryOverNew = (l1==null?0:l1.val + (l2==null?0:l2.val) + carryOver)/10;
recursiveAdd(l1.next, l2.next, l3.next, carryOverNew);
}
}
}

问题： 鉴于我每次都在创建新节点，终止后总是有一个值为 0 的额外节点。如何摆脱这个？ 例：

您的输入 [2,4,3] [5,6,4]

输出 [7,0,8,0]

预期 [7,0,8]

Answer 1

在检查是否确实需要之前，请在结果列表中创建另一个节点。以下是解决此问题的方法：

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode l3 = new ListNode(0);
recursiveAdd(l1, l2, l3, 0);
return l3;
}
private void recursiveAdd(ListNode l1, ListNode l2, ListNode l3, int carryOver){
//calculate value of the current digit
l3.val = ((l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carryOver) % 10;
//calculate carry over to the next digit
int carryOverNew = ((l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carryOver) / 10;
//take the next digit from the two operands
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
//another digit is only needed if at least one these are true:
//1. the first operand has another digit
//2. the second operand has another digit
//3. the carry over is more than zero
if (l1 != null || l2 != null || carryOverNew > 0) {
//only create another digit when it is needed
l3.next = new ListNode(0);
recursiveAdd(l1, l2, l3.next, carryOverNew);
}
}
}

该解决方案已使用示例输入和两个零([0] 和 [0] 正确添加到 [0](进行了测试。

编辑：我在获取 l1 和 l2 的下一个元素之前添加了空检查以防止 NullPointerExceptions，并在计算 l3.val 和 carryOverNew 时在第一个三元运算符 (？:) 周围添加了括号以防止错误结果。