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

Question

PS:有多个帖子介绍了链表表示的两个数字相加，但没有讨论递归解决方案。因此，请不要将投票标记为重复。

Q. You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

我的尝试

/**
 * 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 的额外节点。如何摆脱这个？ 示例:

Your input [2,4,3] [5,6,4]

Output [7,0,8,0]

Expected [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 的下一个元素之前添加了 null 检查以防止 NullPointerExceptions，并在 l3.val 和 CarryOverNew 的计算中在第一个三元运算符 (?:) 周围添加了括号以防止错误结果。