# Easy Java Solution with O(1) space complexity and O(n) time Complexity with an detailed explanation

• ``````     * 1) find the point which the length to the end equals to the shorter one:
*      A->B->C->D and B->D :the point is C in the first list
* 2) calculate recursively for the common area :C->D and B->D;
* 3) get the carry bit of the first calculate : sum;
* 4) calculate recursively for the left of the longer list;
* 5) return the longer list, we record the num in the longer list
*
* */
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) return null;
if (l1 == null) return l2;
if (l2 == null) return l1;

//node[1]: the point which th plus begain;
//node[0]: the head of the long list;
ListNode[] node = findPosition(l1, l2);

if (node[1] == l2) {
int sum = calculate(l1, l2);
if (sum == 1) {
ListNode head = new ListNode(1);
head.next = l1;
return head;
}
return l1;
}else {
if (node[0] == l1) {
int sum = calculate(node[1], l2);
if (sum == 0) return l1;
if (calculate(l1, sum, node[1]) == 1) {
ListNode head = new ListNode(1);
head.next = l1;
return head;
}
return l1;
}else {
int sum = calculate(node[1], l1);
if (sum == 0) return l2;
if (calculate(l2, sum, node[1]) == 1) {
ListNode head = new ListNode(1);
head.next = l2;
return head;
}
return l2;
}
}
}

//calculate one
private int calculate(ListNode l1, ListNode l2) {
if (l1 == null) {
return 0;
}
int sum = l1.val + l2.val + calculate(l1.next, l2.next);
l1.val = sum%10;
sum = sum >= 10 ? 1:0;
return sum;
}
//calculate two
private int calculate(ListNode l1, int sum, ListNode node) {
if (l1 == node) {
return sum;
}
sum = l1.val + calculate(l1.next, sum, node) ;
if (sum == 0) return 0;
l1.val = sum%10;
sum = sum >= 10? 1:0;
return sum;
}

//find point
private ListNode[] findPosition(ListNode l1, ListNode l2) {
ListNode t1 = l1;
ListNode t2 = l2;
ListNode[] tag = new ListNode[2];
while (t1.next != null && t2.next != null) {
t1 = t1.next;
t2 = t2.next;
}
//1） l1 is as long as l2
//2）l1 is longer
//3）l2 is longer
if (t1.next == null && t2.next == null) {
tag[0] = l1;
tag[1] = l2;
}else if (t1.next == null) {
solve (tag, l2, t2);
}else {
solve (tag, l1, t1);
}
return tag;
}
//find the point using former and latter pointer
private void solve(ListNode[] tag, ListNode l, ListNode t) {
tag[0] = l;
ListNode p = l;
while (t.next != null) {
p = p.next;
t = t.next;
}
tag[1] = p;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.