2. Add Two Numbers

Problem

Tags: Linked List, Math, Recursion

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.

Solution

This is a linked problem.

We have a O(n) solution.

Code

GO

// 2. Add Two Numbers (12/14/53371)
// Runtime: 12 ms (55.88%) Memory: 4.75 MB (7.74%) 

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    zero_node := &ListNode{ Val: 0 }
    
    list := &ListNode{ Val: 0 }
    
    pos := list
    
    first, sum, carry := true, l1.Val + l2.Val, 0
    for sum != 0 || l1.Next != nil || l2.Next != nil || first {
        first = false
        carry = sum / 10
        sum = sum % 10
        
        pos.Next = &ListNode{ Val: sum }
        pos = pos.Next
        
        if l1.Next != nil {
            l1 = l1.Next
        } else {
            l1 = zero_node
        }
        if l2.Next != nil {
            l2 = l2.Next
        } else {
            l2 = zero_node
        }
        
        sum = l1.Val + l2.Val + carry
    }
    
    return list.Next
}

JS

// 2. Add Two Numbers (11/9/53371)
// Runtime: 124 ms (62.40%) Memory: 44.15 MB (94.90%) 

/**
 * Definition for singly-linked list.
 * 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 zero_node = new ListNode(0, null);

    let list = new ListNode(undefined, null);

    let pos = list;

    let first = true,
        sum = l1.val + l2.val,
        carry = 0;
    while (sum || l1.next || l2.next || first) {
        first = false;
        carry = parseInt(sum / 10);
        sum = sum % 10;

        pos.next = new ListNode(sum, null);
        pos = pos.next;

        l1 = l1.next || zero_node;
        l2 = l2.next || zero_node;
        
        sum = l1.val + l2.val + carry;
    }

    return list.next;
};

TS

// 2. Add Two Numbers (8/9/54157)
// Runtime: 112 ms (81.89%) Memory: 49.05 MB (12.29%) 

/**
 * Definition for singly-linked list.
 * 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)
 *     }
 * }
 */

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const ans = new ListNode();
    
    let curr = ans,
        carry = 0;
    while (l1 || l2 || carry) {
        const sum = carry + (l1?.val || 0) + (l2?.val || 0);
        carry = Math.floor(sum / 10);
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        
        l1 = l1?.next;
        l2 = l2?.next;
    }

    return ans.next;
};