为什么我的链表添加程序在某些情况下不起作用

Question

所以我有一个 java 程序来添加两个数字，两个数字由 2 个不同的链表表示，每个节点存储一个数字。

我正在尝试编写一个递归解决方案，其中两个链表的总和在第一个链表中并返回。

示例：链表 1= 125

链表 2=149

链表 3 应该包含 274(125+149)。

我的程序在这里：


/**
* 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) {
addnums(l1,l2);
Display(l1);
return l1;
}



public static void addnums(ListNode l1, ListNode l2)    // actual work is done here
{

if(l1!=null && l2!=null)
{
l1.val+=l2.val;
if(l1.val>=10)
l1=carryfwd(l1);
addnums(l1.next,l2.next);
}
else if(l1==null && l2!=null)
{
// l1.val=l2.val;
l1=new ListNode(l2.val);
System.out.println("initialized with "+l1.val);
addnums(l1.next,l2.next);
}
}



public static void Display(ListNode l)
{
while(l!=null)
{
if(l.next==null)
System.out.println(l.val+" ");
else
System.out.print(l.val+" ");
l=l.next;
}
}


public static ListNode carryfwd(ListNode l)    // to carryover to the next node
{
l.val%=10;
if(l.next!=null)
{l.next.val+=1;
if(l.next.val>=10)
carryfwd(l.next);
}
else
l.next=new ListNode(1);
return l;
}

}

此代码不适用于

L1={0}

L2={7,3}

，addTwoNumbers方法返回的L1只有{7}。

尽管我在 addnums 方法的 else 部分将 3 附加到 L1。

请帮助我了解我的 3 节点在哪里丢失。

您可以运行此代码直接位于：https://leetcode.com/problems/add-two-numbers/

Answer 1

主要问题是当 else 块开始时，l1 被分配了一个新值。调用者不会看到此更改，因为 l1 是局部变量。因此，此后发生的事情发生在与原始 l1.

无关的列表上

更深层次的问题是 addnums 函数不能希望在它得到的只是一个 null 值时将新节点附加到第一个列表。

这就是为什么最好坚持使用 addTwoNumbers 函数的原始签名，即 returns 结果列表。在那种情况下，当第一个参数恰好是 null 时没有问题：我们仍然可以创建新节点并 return 它。

另一个说法是：当两个列表节点之一是 null 时，您可以只 return 另一个。在这种情况下无需再发生任何事情。

所以这是一个更正，保留你在 if 块中的代码，这很好：

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // If one of the arguments is null, return the other
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        // Your original logic:
        l1.val += l2.val;
        if (l1.val >= 10)
            l1 = carryfwd(l1);
        l1.next = addTwoNumbers(l1.next, l2.next);
        return l1;
    }

请注意，您可以通过将递归替换为迭代来提高速度，并在下一次迭代中保留刚添加的进位变量。

为什么我的链表添加程序在某些情况下不起作用

Why isn't my linked list addition program working for some cases

java

algorithm

recursion

reference

linked-list