Question

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

2	Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in
reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a

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



Algorithm

Create a new linked list, 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 ​​together, 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

Java

• 

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

}

• // 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(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