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

Issue

So I have a java program to add two numbers, both numbers are represented by 2 different linked lists where each node stores one digit.

I am trying to write a recursive solution where the sum of both linked lists is in the first linked list and that is returned.

example: Linked List 1= 125

Linked List 2=149

Linked List 3 should contain 274(125+149).

My program is here:

/**
* 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;
}

}

This code doesn't work for

L1={0}

L2={7,3}

, the L1 returned by the addTwoNumbers method is {7} only.

Even though I am appending 3 to L1 in the else part of addnums method.

Please help me understand where my 3 node is getting lost.

You can run this code directly at : https://leetcode.com/problems/add-two-numbers/

Solution

The main issue is that when the else block kicks in, l1 is assigned a new value. The caller will not see this change, since l1 is local variable. So what ever happens after that, is happening on a list that is not connected to the original l1.

The deeper problem is that the addnums function cannot hope to attach new nodes to the first list when all it got was a null value.

This is why it is better to stick with the original signature of the addTwoNumbers function, which returns the resulting list. In that case there is no problem when the first argument happens to be null: we can still create the new node and return it.

Another remark is this: when one of the two list nodes is null you can then just return the other. Nothing more needs to happen in that case.

So here is a correction, keeping the code you had in the if block, which was fine:

    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;
    }

Note that you can gain some speed by replacing recursion with iteration, and keeping the carry in variable that just gets added again in the next iteration.

Answered By - trincot