If the length of the two Linked List is `m`

and `n`

respectively, the running complexity of this solution is going to be `O(m+n)`

.

The runtime of this solution on LeetCode is `4ms`

which beats `31.63%`

of the java solutions.

Please feel free to make suggestions in how to improve this.

```
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
final int carry;
// We can't recursively use the given method because it doesn't have
// provisions to deal with carry that may be generated during addition.
return addTwoNumbers(l1, l2, carry=0);
}
protected ListNode addTwoNumbers(ListNode l1, ListNode l2, int carry) {
final ListNode result = new ListNode(carry);
// Even if the listNodes are null, the carry may not be.
// E.g., (9) + (1) = (0 -> 1)
if (l1 == null && l2 == null) {
if (carry != 0) return result;
else return null;
}
if (l1 != null) result.val += l1.val;
if (l2 != null) result.val += l2.val;
// Generate new carry if necessary and adjust the value.
int newCarry = 0;
if (result.val >= 10) {
result.val = result.val % 10;
newCarry = 1;
}
result.next = addTwoNumbers(
l1 != null ? l1.next : null,
l2 != null ? l2.next : null,
newCarry
);
return result;
}
}
```