# Straightforward O(n) Java Solution Without Modifying Input Lists

• ``````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--;

//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);

carry = (a + b + carry) / 10;
i--; j--;
}
}
}
``````

• @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.

• Nice work. Same advice with noob_coder.

• 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;

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);