# O(n) time O(1) space Input intact Java solution

• ``````public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// Foolish way const space and no change on l1 and l2.
if (l1 == null && l2 == null) return null;

int len1 = 0, len2 = 0;
ListNode n1 = l1, n2 = l2;
while (n1 != null) {
len1 ++;
n1 = n1.next;
}

while (n2 != null) {
len2 ++;
n2 = n2.next;
}

if (len1 > len2) { // l1 is always the shorter one.
n1 = l1; // swap head
l1 = l2;
l2 = n1;

int tmp = len1; // swap length
len1 = len2;
len2 = tmp;
}

// Insert extra length
ListNode dummy = new ListNode(0);
ListNode cur = null;
n1 = l2; n2 = l1;
int diff = len2 - len1;
while (diff != 0) {
cur = dummy.next;
dummy.next = new ListNode(n1.val);
dummy.next.next = cur;
n1 = n1.next;
diff --;
}

// now n1 and n2 should have equal length;
while (n1 != null) {
cur = dummy.next;
dummy.next = new ListNode(n1.val + n2.val);
dummy.next.next = cur;
n1 = n1.next; n2 = n2.next;
}

ListNode h = dummy.next;
int c = 0;
ListNode p = null;
while (h != null) {
h.val += c;
c = h.val / 10;
h.val = h.val % 10;
p = h;
h = h.next;
}
if (c == 1) {
p.next = new ListNode(1);
}

// reverse
h = dummy.next;
p = null;
while (h != null) {
if (h.next != null) {
n1 = h;
n2 = h.next;
h = h.next.next;

n2.next = n1;
n1.next = p;
p = n2;

if (h == null)
return n2;
} else {
h.next = p;
return h;
}
}
return null;
}
}
``````

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