Two non-negative integers stored in linked lists in forward order (most significant digit first). Add and return sum as a linked list in forward order.
Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]
Explanation: 7243 + 564 = 7807.
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]
Use two stacks to reverse the digit order, then add from least significant digit, creating result nodes in reverse which we prepend.
- Push all digits of l1 and l2 onto separate stacks
- Pop and add with carry, prepend each result node to answer
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> s1 = new ArrayDeque<>(), s2 = new ArrayDeque<>();
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.isEmpty() || !s2.isEmpty() || carry != 0) {
int sum = carry;
if (!s1.isEmpty()) sum += s1.pop();
if (!s2.isEmpty()) sum += s2.pop();
carry = sum / 10;
ListNode node = new ListNode(sum % 10);
node.next = head;
head = node;
}
return head;
}
Complexity Analysis:
Time complexity: O(m+n)
Space complexity: O(m+n) — stacks