LeetCode 2. Add Two Numbers

Description

https://leetcode.com/problems/add-two-numbers/

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.

Explanation

The question is about performing math addition operation with two linked lists. The result linked list gets values from the sum of two input linked lists. We can just take this process as we are doing addition in columns.

Key point: We need to add a carry just as we do addition in arithmetic. A carry is a digit that is transferred from one column of digits to another column of more significant digits.

• If there are remaining nodes (l1, l2) in both two linked lists, the result linked list node gets value from ((l1.val + l2.val + carry) % 10).
• If there is only one linked list has remaining node, the esult linked list node gets value ((l1.val + carry) % 10 or (l2.val + carry) % 10).
• If neither of the linked lists has remaining nodes, we should check if there is still carryover value.

Java Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;
                
        while (l1 != null && l2 != null) {
            int value = (l1.val + l2.val + carry) % 10;
            carry = (l1.val + l2.val + carry) / 10;
            ListNode result = new ListNode(value);
            current.next = result;
            l1 = l1.next;
            l2 = l2.next;
            current = result;
        }
        
        while (l1 != null) {
            int value = (l1.val + carry) % 10;
            carry = (l1.val + carry) / 10;            
            ListNode result = new ListNode(value);
            current.next = result;
            l1 = l1.next;
            current = result;            
        }
        
        while (l2 != null) {
            int value = (l2.val + carry) % 10;
            carry = (l2.val + carry) / 10;     
            ListNode result = new ListNode(value);
            current.next = result;
            l2 = l2.next;
            current = result;            
        }        
        
        if (carry != 0) {
            ListNode result = new ListNode(carry);
            current.next = result;
            current = result;             
        }
        
        return dummy.next;        
    }
}

Python Solution

# 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:
        dummy = ListNode(0)
        l3 = dummy
        
        carry = 0
        while l1 != None and l2 != None:
            value = (l1.val + l2.val + carry) % 10
            carry = (l1.val + l2.val + carry) // 10
            
            l3.next = ListNode(value) 
            l3 = l3.next

            l1 = l1.next                        
            l2 = l2.next
            

        while l1 != None:
            value = (l1.val + carry) % 10
            carry = (l1.val + carry) // 10
            
            l3.next = ListNode(value) 
            l3 = l3.next
            l1 = l1.next
            
        while l2 != None:
            value = (l2.val + carry) % 10
            carry = (l2.val + carry) // 10
            
            l3.next = ListNode(value)             
            l3 = l3.next
            l2 = l2.next
        
        if carry != 0:
            l3.next = ListNode(carry) 
            
            
        return dummy.next

• Time Complexity: ~max(M, N), where M and N represent the length of l1 and l2 respectively, the algorithm above iterates at most max(M, N) times.
• Space Complexity: ~max(M,N). The length of the new list is at most max(M, N) + 1.