LinkedList 的最后一个值未被解析

Question

我在做一道 leetcode 题：两个数相加

其中一个测试用例没有通过，我不知道为什么我的程序没有最后一个值。这是代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //have to use bit addition here
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }

        int b1=0, b2=0, resBit = 0, carryBit=0;
        ListNode res = new ListNode(-1);
        ListNode dummy = res;

        while(l1!=null && l2!=null){
            resBit = l1.val+l2.val+carryBit;
            if(resBit >9){
                carryBit=1;
                resBit=resBit%10;
            }
            else{
                carryBit=0;
            }
            dummy.next = new ListNode(resBit);
            l1=l1.next;
            l2=l2.next;
            dummy=dummy.next;
        }

        //add any remaining numbers to our result

        if(l1!=null){
            System.out.println(l1.val);
            if(carryBit!=0){
                resBit = l1.val+carryBit;
                if(resBit >9){
                    carryBit=1;
                    resBit=resBit%10;
                }
                else{
                    carryBit=0;
                }
                dummy.next = new ListNode(resBit);
            }
            else{

                dummy.next = new ListNode(l1.val);
            }
            l1=l1.next;
            System.out.println(l1.val);
            dummy=dummy.next;
        }

        if(l2!=null){
            if(carryBit!=0){
                resBit = l2.val+carryBit;
                if(resBit >9){
                    carryBit=1;
                    resBit=resBit%10;
                }
                else{
                    carryBit=0;
                }
                dummy.next = new ListNode(resBit);
            }
            else{
                dummy.next = new ListNode(l2.val);
            }
            l2=l2.next;
            dummy=dummy.next;
        }

        if(carryBit!=0){
            dummy.next = new ListNode(carryBit);
        }


        //remove the -1 used to create the LL initially
        res = res.next;

        return res;
    }
}

以下是失败测试用例的详细信息：

错误答案运行时间：0 毫秒您的输入 [9,1,6] [0]

标准输出 1个 6

输出 [9,1] 预期的 [9,1,6]

如您所见，我的代码遗漏了 6。然而，6 被打印在剩余的 l1 元素解析循环中。为什么会错过？

如果循环未获取运行，则可能会错过它的唯一方法，这意味着程序将 6 获取为 null，因此跳过了一个值。不知道为什么会这样。这是正确的思路吗？

非常感谢任何新信息或改进。

Answer 1

有一种方法可以跳过我的错误方法，并且该解决方案有效。但是，它仍然没有解决原始问题。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //have to use bit addition here
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }

        int b1=0, b2=0, resBit = 0, carryBit=0;
        ListNode res = new ListNode(-1);
        ListNode dummy = res;

        while(l1!=null || l2!=null){
            b1 = (l1 != null) ? l1.val : 0;
            b2 = (l2 != null) ? l2.val : 0;
            resBit = b1+b2+carryBit;
            if(resBit >9){
                carryBit=1;
                resBit=resBit%10;
            }
            else{
                carryBit=0;
            }
            dummy.next = new ListNode(resBit);
            if(l1!=null){
                l1=l1.next;
            }

            if(l2!=null){
                l2=l2.next;
            }

            dummy=dummy.next;
        }

        //add carry to our result if carry is not 0
        if(carryBit!=0){
            dummy.next = new ListNode(carryBit);
        }


        //remove the -1 used to create the LL initially
        res = res.next;
        return res;
    }

正如我所说，此解决方案成功通过了测试用例。但是，我仍然不确定为什么以前的代码不起作用。如果您知道原因，请回复。

Answer 2

作为一点无耻的宣传，请查看 my solution。但我可以指出它不起作用的原因，以及其他一些好的做法首先，b1和b2是干什么用的？我是否遗漏了什么，因为我在您的代码中一次都没有看到它。

这边：

if(resBit >9){
    carryBit=1;
    resBit=resBit%10;
}

您正在将进位位设置为 1。但是，您必须将其设置为 sum / 10，以防总和达到 20 之类的值。在实际问题中，没有任何测试用例会给您带来问题，但是如果数字较大，则会导致错误。

更大的原因是这部分：

if(l1!=null){

和

if(l2!=null){

您只检查一次它是否不为空。但是，如果两个列表的大小相差 2 或更多，则终止时 l1 或 l2 仍将是非空的。因此，您必须将 if 更改为 while 循环。

当我应用这些更改时，它起作用了。这是结果：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //have to use bit addition here
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }

        int resBit = 0, carryBit=0;
        ListNode res = new ListNode(-1);
        ListNode dummy = res;

        while(l1!=null && l2!=null){
            resBit = l1.val+l2.val+carryBit;
            if(resBit >9){
                carryBit=resBit / 10;
                resBit=resBit%10;
            }
            else{
                carryBit=0;
            }
            dummy.next = new ListNode(resBit);
            l1=l1.next;
            l2=l2.next;
            dummy=dummy.next;
        }

        //add any remaining numbers to our result

        while(l1!=null){
            if(carryBit!=0){
                resBit = l1.val+carryBit;
                if(resBit >9){
                    carryBit=1;
                    resBit=resBit%10;
                }
                else{
                    carryBit=0;
                }
                dummy.next = new ListNode(resBit);
            }
            else{

                dummy.next = new ListNode(l1.val);
            }
            l1=l1.next;
            dummy=dummy.next;
        }

        while(l2!=null){
            if(carryBit!=0){
                resBit = l2.val+carryBit;
                if(resBit >9){
                    carryBit=1;
                    resBit=resBit%10;
                }
                else{
                    carryBit=0;
                }
                dummy.next = new ListNode(resBit);
            }
            else{
                dummy.next = new ListNode(l2.val);
            }
            l2=l2.next;
            dummy=dummy.next;
        }

        if(carryBit!=0){
            dummy.next = new ListNode(carryBit);
        }


        //remove the -1 used to create the LL initially
        res = res.next;

        return res;
    }
}

Answer 3

//将任何剩余的数字添加到我们的结果

    if(l1!=null){
        System.out.println(l1.val);
        if(carryBit!=0){
            resBit = l1.val+carryBit;
            if(resBit >9){
                carryBit=1;
                resBit=resBit%10;
            }
            else{
                carryBit=0;
            }
            dummy.next = new ListNode(resBit);
        }
        else{

            dummy.next = new ListNode(l1.val);
        }
        l1=l1.next;
        System.out.println(l1.val);
        dummy=dummy.next;
    }

    if(l2!=null){
        if(carryBit!=0){
            resBit = l2.val+carryBit;
            if(resBit >9){
                carryBit=1;
                resBit=resBit%10;
            }
            else{
                carryBit=0;
            }
            dummy.next = new ListNode(resBit);
        }
        else{
            dummy.next = new ListNode(l2.val);
        }
        l2=l2.next;
        dummy=dummy.next;
    }

    if(carryBit!=0){
        dummy.next = new ListNode(carryBit);
    }

简而言之，使用 while 循环而不是 if。

如您所见，如果 LinkedList 中的任何一个变为空，上面的代码只运行一次。由于您的测试用例是：

L1: [9,1,6]
L2: [0]

如您所见，第一次添加后：

L1指针变为={1}
L2 指针变为{null}。

然后你只做一次 L1 指针的加法，直到 L1 变成 {null}。

您在评论中提供的解决方案中使用 while 循环解决了它。

LinkedList 的最后一个值未被解析

LinkedList last value not getting parsed

java

linked-list

singly-linked-list