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/

## Advertisement

## Answer

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.