2.add-two-numbers.en.md

Problem

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

Problem Description

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 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.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution

Define a new variable carried that represents the carry value during the calculation, and a new linked list
Traverse the two linked lists from the start to the end simultaneously, and calculate the sum of node value from each linked list. The sum of the result and carried would be appended as a new node to the end of the new linked list.

(Image Reference: https://github.com/MisterBooo/LeetCodeAnimation)

Key Point Analysis

1. The characteristics and application of this data structure - linked list

2. Define a variable named carried to replace the role of carry-over, calculate carried after each sum and apply it to the next round's calculation

Code

• Language Support: JS, C++

JavaScript:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  if (l1 === null || l2 === null) return null

  // using dummyHead can simplify linked list's calculation, dummyHead.next points to the new linked list
  let dummyHead = new ListNode(0)
  let cur1 = l1
  let cur2 = l2
  let cur = dummyHead // cur is for the calculation in new linked list
  let carry = 0 // carry-over symbol

  while (cur1 !== null || cur2 !== null) {
    let val1 = cur1 !== null ? cur1.val : 0
    let val2 = cur2 !== null ? cur2.val : 0
    let sum = val1 + val2 + carry
    let newNode = new ListNode(sum % 10) // the result of sum%10 ranges from 0 to 9, which is the value of the current digit
    carry = sum >= 10 ? 1 : 0 // sum>=10, carry=1, so carry-over exists here
    cur.next = newNode
    cur = cur.next

    if (cur1 !== null) {
      cur1 = cur1.next
    }

    if (cur2 !== null) {
      cur2 = cur2.next
    }
  }

  if (carry > 0) {
    // If there's still carry-over in the end, then add a new node
    cur.next = new ListNode(carry)
  }

  return dummyHead.next
};

C++

C++ code is slightly different from the JavaScript code above: the step that checks whether carry equals to 0 is put in the while-loop.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* ret = nullptr;
        ListNode* cur = nullptr;
        int carry = 0;
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            carry += (l1 == nullptr ? 0 : l1->val) + (l2 == nullptr ? 0 : l2->val);
            auto temp = new ListNode(carry % 10);
            carry /= 10;
            if (ret == nullptr) {
                ret = temp;
                cur = ret;
            }
            else {
                cur->next = temp;
                cur = cur->next;
            }
            l1 = l1 == nullptr ? nullptr : l1->next;
            l2 = l2 == nullptr ? nullptr : l2->next;
        }
        return ret;
    }
};

Extension

The singly-linked list also has a recursive structure based on its definition. Therefore, the recursive apporach works on reversing a linked list, as well.

Because a singly-linked list is a linear data structure, the recursive approach means that the use of stack would also be linear. When the linked list's length reaches a certain level, the recursion would result in a stack overflow. Therefore, using recursion to manipulate a linked list is not recommended in reality.

Description

1. Add up the first node of two linked lists, and covert the result to a number between 0 and 10, record the carry-over as well.
2. Proceed to add up the two linked lists after the first node with carry-over recursively
3. Point the next of the head node from the first step to the linked list returned from the second step

C++ Implementation

// Normal recursion
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        return addTwoNumbers(l1, l2, 0);
    }
    
private:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry) {
        if (l1 == nullptr && l2 == nullptr && carry == 0) return nullptr;
        carry += (l1 == nullptr ? 0 : l1->val) + (l2 == nullptr ? 0 : l2->val);
        auto ret = new ListNode(carry % 10);
        ret->next = addTwoNumbers(l1 == nullptr ? l1 : l1->next,
                                 l2 == nullptr ? l2 : l2->next,
                                 carry / 10);
        return ret;
    }
};
// (Similiar) Tail recursion
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = nullptr;
        addTwoNumbers(head, nullptr, l1, l2, 0);
        return head;
    }
    
private:
    void addTwoNumbers(ListNode*& head, ListNode* cur, ListNode* l1, ListNode* l2, int carry) {
        if (l1 == nullptr && l2 == nullptr && carry == 0) return;
        carry += (l1 == nullptr ? 0 : l1->val) + (l2 == nullptr ? 0 : l2->val);
        auto temp = new ListNode(carry % 10);
        if (cur == nullptr) {
            head = temp;
            cur = head;
        } else {
            cur->next = temp;
            cur = cur->next;
        }
        addTwoNumbers(head, cur, l1 == nullptr ? l1 : l1->next, l2 == nullptr ? l2 : l2->next, carry / 10);
    }
};