Return to Question

Problem Description

Updated Question

Problem Description

Updated Solution

#include <cstddef>
#include <iostream>
#include <ostream>
#include <stddef.h>
#include <stdlib.h>

using std::cout;
using std::endl;
using std::ostream;
using std::string;

struct Node
{
    int val;
    Node *next;
    Node(int val) : val(val), next(NULL) {}

    void PrintAllNodes()
    {
        Node *current = new Node(0);
        current = this;
        std::string nodeString = "LinkedList: ";
        int val = 0;
        while(current != NULL)
        {
            val = current->val;
            nodeString = nodeString + " -> ( " + std::to_string(val) + " ) ";
            current = current->next;
        }

        std::cout << nodeString << '\n';
    }

    void Append(int i)
    {
        if (this->next == NULL)
        {
            Node *n = new Node(i);
            this->next = n;
        }
        else { this->next->Append(i); }
    }
};

class Solution
{
    public:
        Node *AddTwoNumbers(Node *l1, Node *l2);
    private:
        Node *AddTwoNumbersHelper(Node *l1, Node *l2, int sum, int carry, Node *current, Node *head);
};
Node *Solution::AddTwoNumbers(Node *l1, Node *l2)
{
    Node *head = new Node(0);
    Node *current = head;

    int sum = 0;
    int carry = 0;

    return AddTwoNumbersHelper(l1, l2, sum, carry, current, head);
}

Node *Solution::AddTwoNumbersHelper(Node *l1, Node *l2, int sum, int carry, Node *current, Node *head)
{
    if (l1 == NULL && l2 == NULL)
    {
        head = head->next;
        return head;
    }

    sum = 0;
    if (l1 == NULL) { sum = l2->val + carry; }
    else if (l2 == NULL) { sum = l1->val + carry; }
    else if (l1 != NULL && l2 != NULL) { sum = l1->val + l2->val + carry; }

    if (sum >= 10)
    {
        carry = sum / 10;
        sum -= 10;
    }
    else { carry = 0; }

    Node *next = new Node(sum);
    current->next = next;

    if (l1 == NULL) { return AddTwoNumbersHelper(l1, l2->next, sum, carry, current->next, head); }
    else if (l2 == NULL) { return AddTwoNumbersHelper(l1->next, l2, sum, carry, current->next, head); }
    else if (l1 != NULL && l2 != NULL) { return AddTwoNumbersHelper(l1->next, l2->next, sum, carry, current->next, head); }

    return head;
}

/**
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * Explanation: 342 + 465 = 807.
 */
void ProveBasicCase()
{
    cout << "\n\nBasic case\n";
    Solution s;

    Node *l1 = new Node(2);
    l1->Append(4);
    l1->Append(3);

    Node *l2 = new Node(5);
    l2->Append(6);
    l2->Append(4);

    Node *n = new Node(0);
    n = s.AddTwoNumbers(l1, l2);
    n->PrintAllNodes();
}

/**
 * Input: (2 -> 4 -> 3) + (5 -> 6)
 * Output: 7 -> 0 -> 4
 * Explanation: 342 + 65 = 407.
 */
void ProveUnEqualListSize()
{
    cout << "\n\nUneven List sizes\n";
    Solution s;

    Node *l1 = new Node(2);
    l1->Append(4);
    l1->Append(3);

    Node *l2 = new Node(5);
    l2->Append(6);

    Node *n = new Node(0);
    n = s.AddTwoNumbers(l1, l2);
    n->PrintAllNodes();
}

/**
 * Input: (9) + (1 -> 9 -> 9 -> 9 -> 8 -> 9 -> 9)
 * Output: 0 -> 0 -> 0 -> 0 -> 9 -> 9 -> 9
 * Explanation: 9 + 9989991 = 9990000
 */
void ProveDoubleCarry()
{
    cout << "\n\nDouble Carry\n";
    Solution s;

    Node *l1 = new Node(9);

    Node *l2 = new Node(1);
    l2->Append(9);
    l2->Append(9);
    l2->Append(9);
    l2->Append(8);
    l2->Append(9);
    l2->Append(9);

    Node *n = new Node(0);
    n = s.AddTwoNumbers(l1, l2);
    n->PrintAllNodes();
}

int main()
{
    cout << "mr.robot prgm running...\n";

    ProveBasicCase();
    ProveUnEqualListSize();
    ProveDoubleCarry();

    return 0;
}