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.
Link to LeetCode. Only code submitted to LeetCode is in AddTwoNumbersHelper
and AddTwoNumbers
What I'd like some feedback on
I've written this so that anyone can Compile and Run this program on their machines using the following:
g++ -std=c++11 -Wall -Wextra -Werror Main.cpp -o main | ./main
I'm looking for feedback on this LeetCode question since I've seen many examples in other languages, but not many in C++. Even the example solution in LeetCode is written in Java.
I'm mainly looking for any ways I can optimize my conditional statements and arithmetic, my using statement, and use of pointers.
#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 ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
void printAllNodes()
{
ListNode *current = new ListNode(0);
current = this;
string nodeString = "LinkedList: ";
int x = 0;
while(current != NULL)
{
x = current->val;
// IMPORTANT
// must compile using C++ 11
// g++ -std=c++11 -Wall -Wextra -Werror Main.cpp -o main | ./main
nodeString = nodeString + " -> ( " + std::to_string(x) + " ) ";
current = current->next;
}
cout << nodeString << endl;
}
};
class Solution
{
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2);
};
ListNode *Solution::addTwoNumbers(ListNode *l1, ListNode *l2)
{
ListNode *node = new ListNode(0);
ListNode *currentNode = new ListNode(0);
currentNode = node;
ListNode *currentL1 = new ListNode(0);
ListNode *currentL2 = new ListNode(0);
currentL1 = l1;
currentL2 = l2;
int sum = 0;
int carry = 0;
while(currentL1 != NULL || currentL2 != NULL)
{
if (currentL1 == NULL)
{
sum = currentL2->val + carry;
carry = 0;
currentL2 = currentL2->next;
} else if (currentL2 == NULL)
{
sum = currentL1->val + carry;
carry = 0;
currentL1 = currentL1->next;
} else
{
sum = currentL1->val + currentL2->val + carry;
carry = 0;
currentL1 = currentL1->next;
currentL2 = currentL2->next;
}
if (sum >= 10)
{
carry = sum / 10;
currentNode->val = sum % 10;
cout << "sum is " << sum << " with carry of " << carry << endl;
} else
{
currentNode->val = sum;
cout << "sum is " << sum << endl;
}
if (currentL1 == NULL && currentL2 == NULL && sum >= 10)
{
currentNode->next = new ListNode(0);
currentNode = currentNode->next;
currentNode->val = carry;
} else if (currentL1 != NULL || currentL2 != NULL)
{
currentNode->next = new ListNode(0);
currentNode = currentNode->next;
}
}
return node;
}
/**
*
* Proves this
* Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
* Output: 7 -> 0 -> 8
* Explanation: 342 + 465 = 807.
*
* NOTE
* non-empty linked lists representing two non-negative integers
*
*/
void proveBasicCase()
{
cout << "\n\nBasic case\n";
Solution s;
ListNode *l1 = new ListNode(2);
ListNode *l1SubA = new ListNode(4);
ListNode *l1SubB = new ListNode(3);
l1SubA->next = l1SubB;
l1->next = l1SubA;
ListNode *l2 = new ListNode(5);
ListNode *l2SubA = new ListNode(6);
ListNode *l2SubB = new ListNode(4);
l2SubA->next = l2SubB;
l2->next = l2SubA;
ListNode *n = new ListNode(0);
n = s.addTwoNumbers(l1, l2);
n->printAllNodes();
}
/**
*
* Proves this
* Input: (2 -> 4 -> 3) + (5 -> 6)
* Output: 7 -> 0 -> 4
* Explanation: 342 + 65 = 407.
*
* NOTE
* non-empty linked lists representing two non-negative integers
*
*/
void proveListSizeNotEqual()
{
cout << "\n\nUneven List sizes\n";
Solution s;
ListNode *l1 = new ListNode(2);
ListNode *l1SubA = new ListNode(4);
ListNode *l1SubB = new ListNode(3);
l1SubA->next = l1SubB;
l1->next = l1SubA;
ListNode *l2 = new ListNode(5);
ListNode *l2SubA = new ListNode(6);
l2->next = l2SubA;
ListNode *n = new ListNode(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
*
* NOTE
* non-empty linked lists representing two non-negative integers
*
*/
void proveDoubleCarry()
{
cout << "\n\nDouble Carry\n";
Solution s;
ListNode *l1 = new ListNode(9);
ListNode *l2 = new ListNode(1);
ListNode *l2SubA = new ListNode(9);
ListNode *l2SubB = new ListNode(9);
ListNode *l2SubC = new ListNode(9);
ListNode *l2SubD = new ListNode(8);
ListNode *l2SubE = new ListNode(9);
ListNode *l2SubF = new ListNode(9);
l2SubE->next = l2SubF;
l2SubD->next = l2SubE;
l2SubC->next = l2SubD;
l2SubB->next = l2SubC;
l2SubA->next = l2SubB;
l2->next = l2SubA;
ListNode *n = new ListNode(0);
n = s.addTwoNumbers(l1, l2);
n->printAllNodes();
}
int main()
{
using std::cout;
using std::endl;
cout << "Mr Robot is running prgm..." << endl;
proveBasicCase();
proveListSizeNotEqual();
proveDoubleCarry();
return 0;
}
std::list
. If it is explicit necessary, you could add iterator support for your custom implementation and do that task with thestd::transform
algorithm. \$\endgroup\$&& ./main
, rather than| ./main
, for your build+run command? \$\endgroup\$