# O(n) Just Plain Traversal (No Extraspace / No modification to input lists) Beats 64%

• Idea : Get the lengths of both the lists.O(n). create a result list with the sum of digits at respective positions(these additions might contains >10 (ignore carry for now)) O(n). reverse the result list O(n) without extra space. Next compute the carry and modify the value in the node. For the final result reverse the result list again. O(n).

``````public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int l1len = 0, l2len = 0, l1l, l2l;
ListNode temp;
temp = l1;
while(temp!= null){
temp = temp.next;
l1len++;
}
temp = l2;
while(temp!= null){
temp = temp.next;
l2len++;
}

if(l1len==0) return l2;
if(l2len==0) return l1;
if(l1len < l2len) {
temp  = l1 ;
l1 = l2;
l2 = temp;
l2l = l1len;
l1l = l2len;
}else{
l1l = l1len;
l2l = l2len;
}
ListNode head = null, prev = null;
while(l1l != l2l) {
temp = new ListNode(l1.val);
else{
prev.next = temp;
prev = temp;
}
l1 = l1.next;
l1l--;
}

while(l1l >0 && l2l >0){
temp = new ListNode(l1.val + l2.val);
else{
prev.next = temp;
prev = temp;
}
l1 = l1.next; l2 = l2.next;
l1l--; l2l--;
}

}

public ListNode reverse(ListNode node){
ListNode prev = null, head = node, next, temp = node;
while(temp != null){
next = temp.next;
temp.next = prev;
prev = temp;
temp = next;
}
return prev;
}

int carry = 0;