Solving the 'Add Two Numbers' problem on LeetCode with C++

Problem

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

Answer

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(); 
        ListNode* temp = dummy;
        int carry = 0; 

        while(l1 != NULL || l2 != NULL || carry){ 
            int sum = 0; 
            if(l1 != NULL){
                sum += l1->val; 
                l1 = l1->next; 
            }
            if(l2 != NULL){
                sum += l2->val; 
                l2 = l2->next; 
            }
            sum += carry; 
            carry = sum / 10; 
            ListNode* newnode = new ListNode(sum % 10); 
            temp->next = newnode;
            temp = temp->next; 
        }
        return dummy->next;

Firstly, let's consider the expected output.

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

We can obtain the output by summing the numbers from l1 and l2 in order.

2 + 5 = 7
4 + 6 = 10 -> 0 // 4 + 6 = 10. Carry 1 to the next digit and truncate the remaining digits. 
3 + 4 = 7 -> 7 + 1 = 8 // Add 1 carried over from the previous digit.

Output: 7, 0, 8

Now we need to represent this operation in the code.

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(); 
        ListNode* temp = dummy;
        int carry = 0;

We define dummy as a variable of type ListNode* because the function result is ListNode*.

We define the temp variable to reference the dummy pointer, because we need to reference each node to sum each digit.

We define the carry variable to store the carried over number.

        while(l1 != NULL || l2 != NULL || carry){ 
            int sum = 0; 
            if(l1 != NULL){
                sum += l1->val; 
                l1 = l1->next; 
            }
            if(l2 != NULL){
                sum += l2->val; 
                l2 = l2->next; 
            }

We need to calculate all l1 and l2 numbers.
This means we must continue calculation until l1 and l2 are NULL and carry is 0.

If l1 is not NULL, we add the value of l1 to the sum variable.
We move the l1 pointer to the next pointer because the current l1 value has been calculated.

We do the same for l2.

            sum += carry; 
            carry = sum / 10; 
            ListNode* newnode = new ListNode(sum % 10); 
            temp->next = newnode;
            temp = temp->next; 
        }
        return dummy->next;

If there's a carry from a previous digit, we need to add it to the sum variable and update carry with the new value that needs to be carried over to the next digit.

The first digit of the sum should be assigned to a new Node, and this new Node should be assigned to temp->next.
This adds the new Node to the dummy ListNode, but we don't assign the new Node to dummy->next directly.

Because dummy and temp have same pointer.

The reason for this is that we need to return the head of the new ListNode at the end of the function.

Here, temp is a pointer used for calculating l1 and l2, and dummy is a pointer used to return the head of the new ListNode.

Blog

Solving the 'Add Two Numbers' problem on LeetCode with C++

Shiki Endou

Problem

Answer

Join Our Newsletter. No Spam, Only the good stuff.

Related