时间戳

首页 > 解决方案 > 在java中使用递归添加两个由链表表示的数字

java - 在java中使用递归添加两个由链表表示的数字

问题描述

PS：有多个关于添加两个由链表表示的数字的帖子，但没有一个讨论递归解决方案。所以请不要标记为downvote的重复。

问：给定两个代表两个非负整数的非空链表。这些数字以相反的顺序存储，它们的每个节点都包含一个数字。将两个数字相加并将其作为链表返回。

您可以假设这两个数字不包含任何前导零，除了数字 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]

标签： javarecursionlinked-list

解决方案

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

/**
 * 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 时在第一个三元运算符 (?:) 周围添加括号以防止错误结果。

推荐阅读