# Question

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

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

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

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.


Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]


Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]


Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

# Algorithm

Create a new LinkedList, and then push the input two linked lists from the beginning to the back, add every two, and add a new node to the back of the new linked list.

In order to prevent the two input linked lists from being empty at the same time, we create a dummy node, and add the new nodes generated by the addition of the two nodes to the dummy node in order.

Since the dummy node itself cannot be changed, a pointer is used cur to point to the last node of the new linked list. Ok, you can start to add the two linked lists.

This problem is good because the lowest bit is at the beginning of the linked list, so you can directly add them in order from low to high while traversing the linked list. The condition of the while loop, as long as one of the two linked lists is not an empty row, since the linked list may be empty, when taking the current node value, judge first, if it is empty then value is 0, otherwise take the node value.

Then add the two node values, and add carry. Then update carry, directly sum/10, and then create a new node with sum%10 as the value, connect it to the back of cur, and then move cur to the next node.

Then update the two nodes, if they exist, point to the next location. After the while loop exits, the highest carry issue needs to be dealt with specially. If carry is 1, then another node with value 1 is created.

# Code

• 

public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) {
return l1 == null ? l2 : l1;
}

// boolean style, 0 or 1
int carry = 0;

ListNode dummy = new ListNode(0);
ListNode dummyCopy = dummy;

while (l1 != null || l2 != null) {
int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;

// append to result list
dummy.next = new ListNode(sum % 10);
carry = sum >= 10 ? 1 : 0;

// move to next node
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
dummy = dummy.next;
}

// @note: I missed final check
if (carry == 1) {
dummy.next = new ListNode(carry);
}

return dummyCopy.next;
}
}

}

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

/**
* 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) {
ListNode dummy = new ListNode(0);
int carry = 0;
ListNode cur = dummy;
while (l1 != null || l2 != null || carry != 0) {
int s = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
carry = s / 10;
cur.next = new ListNode(s % 10);
cur = cur.next;
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
}
return dummy.next;
}
}

• // OJ: https://leetcode.com/problems/add-two-numbers/
// Time: O(N)
// Space: O(1)
class Solution {
public:
ListNode* addTwoNumbers(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;
}
};

• # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
dummy = ListNode()
carry, curr = 0, dummy
while l1 or l2 or carry:
s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
carry, val = divmod(s, 10)
curr.next = ListNode(val)
curr = curr.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next

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

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

class Solution(object):
# maybe standard version
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
p = dummy = ListNode(-1)
carry = 0
while l1 and l2:
p.next = ListNode(l1.val + l2.val + carry)
carry = p.next.val // 10
p.next.val %= 10
p = p.next
l1 = l1.next
l2 = l2.next

res = l1 or l2
while res:
p.next = ListNode(res.val + carry)
carry = p.next.val // 10
p.next.val %= 10
p = p.next
res = res.next
if carry:
p.next = ListNode(1)
return dummy.next

# shorter version
p = dummy = ListNode(-1)
carry = 0
while l1 or l2 or carry:
val = (l1 and l1.val or 0) + (l2 and l2.val or 0) + carry
carry = val // 10
p.next = ListNode(val % 10)
l1 = l1 and l1.next
l2 = l2 and l2.next
p = p.next
return dummy.next


• /**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
carry := 0
cur := dummy
for l1 != nil || l2 != nil || carry != 0 {
s := carry
if l1 != nil {
s += l1.Val
}
if l2 != nil {
s += l2.Val
}
carry = s / 10
cur.Next = &ListNode{s % 10, nil}
cur = cur.Next
if l1 != nil {
l1 = l1.Next
}
if l2 != nil {
l2 = l2.Next
}
}
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)
*     }
* }
*/

l1: ListNode | null,
l2: ListNode | null,
): ListNode | null {
const dummy = new ListNode();
let cur = dummy;
let sum = 0;
while (sum !== 0 || l1 != null || l2 != null) {
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
cur.next = new ListNode(sum % 10);
cur = cur.next;
sum = Math.floor(sum / 10);
}
return dummy.next;
}


• /**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function (l1, l2) {
const dummy = new ListNode();
let carry = 0;
let cur = dummy;
while (l1 || l2 || carry) {
const s = (l1?.val || 0) + (l2?.val || 0) + carry;
carry = Math.floor(s / 10);
cur.next = new ListNode(s % 10);
cur = cur.next;
l1 = l1?.next;
l2 = l2?.next;
}
return dummy.next;
};


• # Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} l1
# @param {ListNode} l2
# @return {ListNode}
dummy = ListNode.new()
carry = 0
cur = dummy
while !l1.nil? || !l2.nil? || carry > 0
s = (l1.nil? ? 0 : l1.val) + (l2.nil? ? 0 : l2.val) + carry
carry = s / 10
cur.next = ListNode.new(s % 10)
cur = cur.next
l1 = l1.nil? ? l1 : l1.next
l2 = l2.nil? ? l2 : l2.next
end
dummy.next
end

• /**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int val=0, ListNode next=null) {
*         this.val = val;
*         this.next = next;
*     }
* }
*/
public class Solution {
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
int carry = 0;
ListNode cur = dummy;
while (l1 != null || l2 != null || carry != 0) {
int s = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
carry = s / 10;
cur.next = new ListNode(s % 10);
cur = cur.next;
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
}
return dummy.next;
}
}

• import std/[strutils, algorithm]

type
Node[int] = ref object
value: int
next: Node[int]

proc append[T](list: var SinglyLinkedList[T], data: T = nil): void =
var node = Node[T](value: data)
list.tail = node
else:
list.tail.next = node
list.tail = node

var s: seq[T]
while not n.isNil:
n = n.next
result = s.join(" -> ")

var
psum: seq[char]
temp_la, temp_lb: seq[int]

psum = reversed($(reversed(temp_la).join("").parseInt() + reversed(temp_lb).join("").parseInt())) for i in psum: aggregate.append(($i).parseInt())

result = aggregate

for i in @[2, 4, 3]: list1.append(i)
for i in @[5, 6, 4]: list2.append(i)

echo(preview(list1))
echo(preview(list2))


• // 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 {
mut l1: Option<Box<ListNode>>,
mut l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
let mut dummy = Some(Box::new(ListNode::new(0)));
let mut cur = &mut dummy;
let mut sum = 0;
while l1.is_some() || l2.is_some() || sum != 0 {
if let Some(node) = l1 {
sum += node.val;
l1 = node.next;
}
if let Some(node) = l2 {
sum += node.val;
l2 = node.next;
}
cur.as_mut().unwrap().next = Some(Box::new(ListNode::new(sum % 10)));
cur = &mut cur.as_mut().unwrap().next;
sum /= 10;
}
dummy.unwrap().next.take()
}
}


• /**
* public class ListNode {
*     public var val: Int
*     public var next: ListNode?
*     public init() { self.val = 0; self.next = nil; }
*     public init(_ val: Int) { self.val = val; self.next = nil; }
*     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
var dummy = ListNode.init()
var carry = 0
var l1 = l1
var l2 = l2
var cur = dummy
while l1 != nil || l2 != nil || carry != 0 {
let s = (l1?.val ?? 0) + (l2?.val ?? 0) + carry
carry = s / 10
cur.next = ListNode.init(s % 10)
cur = cur.next!
l1 = l1?.next
l2 = l2?.next
}
return dummy.next
}
}