# Question

Formatted question description: https://leetcode.ca/all/445.html

You are given two linked lists representing two non-negative numbers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7



# Algorithm

This question is an extension of the previous Add Two Numbers. We can see that the highest position of this question is at the top of the linked list. If we flip the linked list, it will be the same as the previous question.

Here we look at some unmodified ones. The method of linked list order. Since addition needs to start from the lowest bit, and the lowest bit is at the end of the linked list, the linked list can only be traversed from the front to the back, and the previous elements cannot be retrieved.

What should I do? We can use the stack to store all the elements, and then use the last-in-first-out feature of the stack to fetch numbers from back to front.

We first traverse the two linked lists and push all the numbers into the two stacks s1 and s2. We create a res node with a value of 0, and then start the loop. If the stack is not empty, add the top number of the stack to sum, then assign the res node value to sum%10, and then create a new carry node head, and assign it to sum /10, if there is no carry, then it is 0, and then we connect res after the head, and point res to head, so that after the loop exits, we only need to see if the value of res is 0, if it is 0, return res->next, not 0 Just return res, see the code as follows:

# Code

C++

class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1, s2;
while (l1) {
s1.push(l1->val);
l1 = l1->next;
}
while (l2) {
s2.push(l2->val);
l2 = l2->next;
}
int sum = 0;
ListNode *res = new ListNode(0);
while (!s1.empty() || !s2.empty()) {
if (!s1.empty()) {sum += s1.top(); s1.pop();}
if (!s2.empty()) {sum += s2.top(); s2.pop();}
res->val = sum % 10;
ListNode *head = new ListNode(sum / 10);
sum /= 10;
}
return res->val == 0 ? res->next : res;
}
};


• /**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<ListNode> stack1 = new Stack<ListNode>();
Stack<ListNode> stack2 = new Stack<ListNode>();
ListNode temp1 = l1, temp2 = l2;
while (temp1 != null) {
stack1.push(temp1);
temp1 = temp1.next;
}
while (temp2 != null) {
stack2.push(temp2);
temp2 = temp2.next;
}
Stack<ListNode> stackSum = new Stack<ListNode>();
int carry = 0;
while (!stack1.isEmpty() && !stack2.isEmpty()) {
ListNode node1 = stack1.pop(), node2 = stack2.pop();
int curVal = carry + node1.val + node2.val;
carry = curVal / 10;
curVal %= 10;
ListNode nodeSum = new ListNode(curVal);
if (!stackSum.isEmpty())
nodeSum.next = stackSum.peek();
stackSum.push(nodeSum);
}
while (!stack1.isEmpty()) {
ListNode node1 = stack1.pop();
int curVal = carry + node1.val;
carry = curVal / 10;
curVal %= 10;
ListNode nodeSum = new ListNode(curVal);
if (!stackSum.isEmpty())
nodeSum.next = stackSum.peek();
stackSum.push(nodeSum);
}
while (!stack2.isEmpty()) {
ListNode node2 = stack2.pop();
int curVal = carry + node2.val;
carry = curVal / 10;
curVal %= 10;
ListNode nodeSum = new ListNode(curVal);
if (!stackSum.isEmpty())
nodeSum.next = stackSum.peek();
stackSum.push(nodeSum);
}
while (carry > 0) {
int curVal = carry % 10;
carry /= 10;
ListNode curNode = new ListNode(curVal);
if (!stackSum.isEmpty())
curNode.next = stackSum.peek();
stackSum.push(curNode);
}
return stackSum.peek();
}
}

############

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> s1 = new ArrayDeque<>();
Deque<Integer> s2 = new ArrayDeque<>();
for (; l1 != null; l1 = l1.next) {
s1.push(l1.val);
}
for (; l2 != null; l2 = l2.next) {
s2.push(l2.val);
}
int carry = 0;
ListNode dummy = new ListNode();
while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
carry += (s1.isEmpty() ? 0 : s1.pop()) + (s2.isEmpty() ? 0 : s2.pop());
ListNode node = new ListNode(carry % 10, dummy.next);
dummy.next = node;
carry /= 10;
}
return dummy.next;
}
}

• // OJ: https://leetcode.com/problems/add-two-numbers-ii/
// Time: O(N)
// Space: O(1)
class Solution {
ListNode *reverse(ListNode *h) {
ListNode dummy;
while (h) {
auto p = h;
h = h->next;
p->next = dummy.next;
dummy.next = p;
}
return dummy.next;
}
ListNode* add(ListNode* a, ListNode* b) {
int carry = 0;
ListNode dummy, *tail = &dummy;
while (a || b || carry) {
if (a) {
carry += a->val;
a = a->next;
}
if (b) {
carry += b->val;
b = b->next;
}
tail->next = new ListNode(carry % 10);
tail = tail->next;
carry /= 10;
}
return dummy.next;
}
public:
ListNode* addTwoNumbers(ListNode* a, ListNode* b) {
a = reverse(a);
b = reverse(b);
}
};

• # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
s1, s2 = [], []
while l1:
s1.append(l1.val)
l1 = l1.next
while l2:
s2.append(l2.val)
l2 = l2.next
carry, dummy = 0, ListNode()
while s1 or s2 or carry:
carry += (0 if not s1 else s1.pop()) + (0 if not s2 else s2.pop())
carry, val = divmod(carry, 10)
node = ListNode(val, dummy.next)
dummy.next = node
return dummy.next

############

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""

def r(root):
pre = None
cur = root
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre

p = dummy = ListNode(-1)
p1, p2 = r(l1), r(l2)
pre = None
carry = 0
while p1 and p2:
p.next = ListNode(p1.val + p2.val + carry)
carry = 1 if p.next.val > 9 else 0
p.next.val = p.next.val % 10
p1 = p1.next
p2 = p2.next
p = p.next
pp = p1 or p2
while pp:
p.next = ListNode(pp.val + carry)
carry = 1 if p.next.val > 9 else 0
p.next.val = p.next.val % 10
pp = pp.next
p = p.next
if carry:
n = ListNode(1)


• /**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
s1, s2 := arraystack.New(), arraystack.New()
for l1 != nil {
s1.Push(l1.Val)
l1 = l1.Next
}
for l2 != nil {
s2.Push(l2.Val)
l2 = l2.Next
}
carry, dummy := 0, new(ListNode)
for !s1.Empty() || !s2.Empty() || carry > 0 {
v, ok := s1.Pop()
if ok {
carry += v.(int)
}
v, ok = s2.Pop()
if ok {
carry += v.(int)
}
node := &ListNode{Val: carry % 10, Next: dummy.Next}
dummy.Next = node
carry /= 10
}
return dummy.Next
}

• /**
* class ListNode {
*     val: number
*     next: ListNode | null
*     constructor(val?: number, next?: ListNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.next = (next===undefined ? null : next)
*     }
* }
*/

const createStack = (head: ListNode | null) => {
const res = [];
}
return res;
};

l1: ListNode | null,
l2: ListNode | null,
): ListNode | null {
const stack1 = createStack(l1);
const stack2 = createStack(l2);
const dummy = new ListNode();
let sum = 0;
while (stack1.length !== 0 || stack2.length !== 0 || sum !== 0) {
sum += (stack1.pop() ?? 0) + (stack2.pop() ?? 0);
dummy.next = new ListNode(sum % 10, dummy.next);
sum = Math.floor(sum / 10);
}
return dummy.next;
}


• // Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
fn create_stack(mut head: Option<Box<ListNode>>) -> Vec<i32> {
let mut res = vec![];
while let Some(node) = head {
res.push(node.val);
}
res
}

l1: Option<Box<ListNode>>,
l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
let mut stack1 = Self::create_stack(l1);
let mut stack2 = Self::create_stack(l2);

let mut dummy = Box::new(ListNode::new(0));
let mut sum = 0;
while !stack1.is_empty() || !stack2.is_empty() || sum != 0 {
if let Some(val) = stack1.pop() {
sum += val;
}
if let Some(val) = stack2.pop() {
sum += val;
}
dummy.next = Some(Box::new(ListNode {
val: sum % 10,
next: dummy.next.take(),
}));
sum /= 10;
}
dummy.next.take()
}
}