# O(n) Java Solution without using stack or recursion. Space O(1)

• ``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode cur1 = l1, cur2 = l2;
int size1 = 0, size2 = 0;
while (cur1 != null){
size1++;
cur1 = cur1.next;
}
while (cur2 != null){
size2++;
cur2 = cur2.next;
}

if (size1 < size2){
ListNode temp = l1;
l1 = l2;
l2 = temp;
int size = size1;
size1 = size2;
size2 = size;
}
cur1 = l1;
cur2 = l2;
for (int i = size1 - size2; i > 0; i--){
ListNode sumNode = new ListNode(cur1.val);
sumCur.next = sumNode;
if (sumNode.val < 9){
sumPre = sumNode;
}
sumCur = sumNode;
cur1 = cur1.next;
}

while (cur1 != null){
ListNode sumNode = new ListNode(cur1.val + cur2.val);
sumCur.next = sumNode;
if (sumNode.val >= 10){
sumNode.val -= 10;
sumPre.val += 1;
while (sumPre != sumCur){
sumPre = sumPre.next;
sumPre.val = 0;
}
sumPre = sumNode;
} else if (sumNode.val < 9){
sumPre = sumNode;
}
sumCur = sumNode;
cur1 = cur1.next;
cur2 = cur2.next;
}