public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
HashMap<Integer, Integer> hm1 = new HashMap<>(); //Store the 'index' and the value of List1
HashMap<Integer, Integer> hm2 = new HashMap<>(); //Store the 'index' and the value of List2
int i = 1, j = 1;
while(l1 != null){
hm1.put(i, l1.val);
l1 = l1.next;
i++;
}
while(l2 != null){
hm2.put(j, l2.val);
l2 = l2.next;
j++;
}
int carry = 0;
i; j;
ListNode head = null;
//Create new nodes to the front of a new LinkedList
while(i > 0  j > 0  carry > 0){
int a = i > 0 ? hm1.get(i) : 0;
int b = j > 0 ? hm2.get(j) : 0;
int res = (a + b + carry) % 10;
ListNode newNode = new ListNode(res);
newNode.next = head;
head = newNode;
carry = (a + b + carry) / 10;
i; j;
}
return head;
}
}
Straightforward O(n) Java Solution Without Modifying Input Lists


@ZachC
If you initialize i = 0 and j = 0, then there wont be a need to decrement them both before the 3rd while loop, right ? We can avoid the 2 decrement statements.


Use a stack instead of a HashMap will save you space and also will get rid of the decrement statements.
Stack<Integer> s1 = new Stack<Integer>(); Stack<Integer> s2 = new Stack<Integer>(); while (l1 != null) { s1.push(l1.val); l1 = l1.next; } while (l2 != null) { s2.push(l2.val); l2 = l2.next; } int carry = 0; ListNode head = null; while(!s1.empty()  !s2.empty()  carry != 0) { if (!s1.empty()) { carry += s1.pop(); } if (!s2.empty()) { carry += s2.pop(); } ListNode node = new ListNode(carry % 10); node.next = head; head = node; carry /= 10; } return head;