Add Two Numbers given in Reverse Order from a Linked List

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;







up vote
7
down vote

favorite












Updated Question



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 

 cout << nodeString << endl;
 
;

class Solution

 public:
 ListNode *addTwoNumbers(ListNode *l1, ListNode *l2);
;
ListNode *Solution::addTwoNumbers(ListNode *l1, ListNode *l2)
 currentL2 != 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 << "nnBasic casen";
 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 << "nnUneven List sizesn";
 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 << "nnDouble Carryn";
 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;




c++ linked-list mathematics pointers gcc




share|improve this question


















  • 3




    It seems a little bit odd to implement a custom solution for a linked list instead of simply using std::list. If it is explicit necessary, you could add iterator support for your custom implementation and do that task with the std::transform algorithm.
    – DNK
    Aug 17 at 18:21










  • @Greg, you might be interested in this question.
    – Incomputable
    Aug 18 at 20:18






  • 1




    Since you've already been told that updating the solution is not appropriate for this site, this is just to direct you to the full explanation :) see what you may and may not do after receiving answers for the reason behind the policy. Thanks!
    – Vogel612♦
    Aug 25 at 16:52










  • Did you mean && ./main, rather than | ./main, for your build+run command?
    – Toby Speight
    Aug 27 at 7:21
















up vote
7
down vote

favorite












Updated Question



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 

 cout << nodeString << endl;
 
;

class Solution

 public:
 ListNode *addTwoNumbers(ListNode *l1, ListNode *l2);
;
ListNode *Solution::addTwoNumbers(ListNode *l1, ListNode *l2)
 currentL2 != 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 << "nnBasic casen";
 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 << "nnUneven List sizesn";
 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 << "nnDouble Carryn";
 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;




c++ linked-list mathematics pointers gcc




share|improve this question


















  • 3




    It seems a little bit odd to implement a custom solution for a linked list instead of simply using std::list. If it is explicit necessary, you could add iterator support for your custom implementation and do that task with the std::transform algorithm.
    – DNK
    Aug 17 at 18:21










  • @Greg, you might be interested in this question.
    – Incomputable
    Aug 18 at 20:18






  • 1




    Since you've already been told that updating the solution is not appropriate for this site, this is just to direct you to the full explanation :) see what you may and may not do after receiving answers for the reason behind the policy. Thanks!
    – Vogel612♦
    Aug 25 at 16:52










  • Did you mean && ./main, rather than | ./main, for your build+run command?
    – Toby Speight
    Aug 27 at 7:21












up vote
7
down vote

favorite









up vote
7
down vote

favorite











Updated Question



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 

 cout << nodeString << endl;
 
;

class Solution

 public:
 ListNode *addTwoNumbers(ListNode *l1, ListNode *l2);
;
ListNode *Solution::addTwoNumbers(ListNode *l1, ListNode *l2)
 currentL2 != 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 << "nnBasic casen";
 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 << "nnUneven List sizesn";
 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 << "nnDouble Carryn";
 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;




c++ linked-list mathematics pointers gcc




share|improve this question














Updated Question



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 

 cout << nodeString << endl;
 
;

class Solution

 public:
 ListNode *addTwoNumbers(ListNode *l1, ListNode *l2);
;
ListNode *Solution::addTwoNumbers(ListNode *l1, ListNode *l2)
 currentL2 != 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 << "nnBasic casen";
 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 << "nnUneven List sizesn";
 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 << "nnDouble Carryn";
 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;





c++ linked-list mathematics pointers gcc





share|improve this question













share|improve this question




share|improve this question








edited Aug 25 at 16:51

























asked Aug 17 at 17:34









greg

23117




23117







  • 3




    It seems a little bit odd to implement a custom solution for a linked list instead of simply using std::list. If it is explicit necessary, you could add iterator support for your custom implementation and do that task with the std::transform algorithm.
    – DNK
    Aug 17 at 18:21










  • @Greg, you might be interested in this question.
    – Incomputable
    Aug 18 at 20:18






  • 1




    Since you've already been told that updating the solution is not appropriate for this site, this is just to direct you to the full explanation :) see what you may and may not do after receiving answers for the reason behind the policy. Thanks!
    – Vogel612♦
    Aug 25 at 16:52










  • Did you mean && ./main, rather than | ./main, for your build+run command?
    – Toby Speight
    Aug 27 at 7:21












  • 3




    It seems a little bit odd to implement a custom solution for a linked list instead of simply using std::list. If it is explicit necessary, you could add iterator support for your custom implementation and do that task with the std::transform algorithm.
    – DNK
    Aug 17 at 18:21










  • @Greg, you might be interested in this question.
    – Incomputable
    Aug 18 at 20:18






  • 1




    Since you've already been told that updating the solution is not appropriate for this site, this is just to direct you to the full explanation :) see what you may and may not do after receiving answers for the reason behind the policy. Thanks!
    – Vogel612♦
    Aug 25 at 16:52










  • Did you mean && ./main, rather than | ./main, for your build+run command?
    – Toby Speight
    Aug 27 at 7:21







3




3




It seems a little bit odd to implement a custom solution for a linked list instead of simply using std::list. If it is explicit necessary, you could add iterator support for your custom implementation and do that task with the std::transform algorithm.
– DNK
Aug 17 at 18:21




It seems a little bit odd to implement a custom solution for a linked list instead of simply using std::list. If it is explicit necessary, you could add iterator support for your custom implementation and do that task with the std::transform algorithm.
– DNK
Aug 17 at 18:21












@Greg, you might be interested in this question.
– Incomputable
Aug 18 at 20:18




@Greg, you might be interested in this question.
– Incomputable
Aug 18 at 20:18




1




1




Since you've already been told that updating the solution is not appropriate for this site, this is just to direct you to the full explanation :) see what you may and may not do after receiving answers for the reason behind the policy. Thanks!
– Vogel612♦
Aug 25 at 16:52




Since you've already been told that updating the solution is not appropriate for this site, this is just to direct you to the full explanation :) see what you may and may not do after receiving answers for the reason behind the policy. Thanks!
– Vogel612♦
Aug 25 at 16:52












Did you mean && ./main, rather than | ./main, for your build+run command?
– Toby Speight
Aug 27 at 7:21




Did you mean && ./main, rather than | ./main, for your build+run command?
– Toby Speight
Aug 27 at 7:21










5 Answers
5






active

oldest

votes

















up vote
7
down vote



accepted










Don't write your own container classes when there's no need



The problem you describe involves working with lists, not implementing a list data structure. Use a ready-made list from the standard library - std::list should be fine. So, essentially you need to implement the following function:



using digit_t = uint8_t; // or unsigned char if you like
using num_in_list_t = std::list<digit_t>;

num_in_list_t add(const num_in_list_t& l1, const num_in_list_t& l2);


Mark const where relevant



Your addTwoNumbers() function takes non-const ListNode *s. This suggests you may intend to change the pointed-to data - which you do not.



Don't implement your own pretty-printer



You can use Louis Delacroix's effective cxx pretty printer; it might not do exactly what you want, but again - why make your life difficult for no reason?



Follow best practices for memory management



With modern C++, you should:



  • Avoid using new and delete directly

  • Avoid using raw pointers which own the pointed-to data

Instead, use smart pointers; specifically, allocate with std::make_unique (C++14), to get an allocation which will be released automatically and never leak. Of course - if you used std::list, you wouldn't have to allocate anything anyway.



More on this in C++ Core guidelines Section R: See guidelines R.10, R.11, R.20, R.21, R.23.



Don't rush to optimize



The question is about correctness and elegance, not performance (or at least - it should be). You should only care about minizing the time (and space) complexity should be, and not going over that - and indeed, you have kept your implementation to O(1) extra space and O(|l1|+|l2|) time. That's enough.



De-spaghetti-ize your main loop



Your main loop code is a bit long, and could be made clearer with a bit of work. At the very least you should add comments, but a better alternative would be to change the code to be more self-documenting.



Don't be afraid of recursion



It's often easier to solve problems on linearly-iterable data recursively - doing something with the head, doing something with the tail, and finishing up if need be. This is also the case for you, except that the recursive case can involve an advance in either one list or the other.






share|improve this answer


















  • 1




    Thanks a lot, this explanation is very clear and helpful. only questions I have are how did you compute the space complexity and can you give some more guidance on how to make the code more self documenting / de-spaghetti-ize it?
    – greg
    Aug 17 at 19:28






  • 1




    @GregDegruy: Start by following the rest of the advice; post it as a new question here; and post a comment here with a link to it.
    – einpoklum
    Aug 18 at 7:28






  • 2




    @GregDegruy: Also, if you follow my "don't be afraid of recursion" advice, you should get nice, clean, short code.
    – einpoklum
    Aug 18 at 8:25

















up vote
6
down vote













As @einpoklum already went into reusing existing code, I'll dive deeper into the algorithm used.



Current algorithm



Until the end of both lists reached:



  1. Get a sum, taking into account if one of them is null


  2. Assign the sum to current node, raising carry flag through branching


  3. ...


And that's as much as I could dive into it, since it became too hard to deal with branching and parts of code being in different places.



Proposed algorithm



Let me show the algorithm I would implement:



Until either end is reached:



  1. Take the sum plus the carry


  2. If sum is greater than 9, substract 10 and raise the carry flag


  3. Advance lists by one, including the output list


When either end is reached, just bump the remaining one, taking carry into account. Reverse the resulting list, to finish the last requirement.



Implementation of proposed algorithm



Standard library evangelist might march on with iterator support, but then will be disappointed:



template <typename InputIterator, typename OutputIterator>
auto fill_rest(InputIterator first, InputIterator last, 
 OutputIterator d_first, bool has_carry) 
 for (; first != last; ++first) 
 auto digit = *first;
 digit += has_carry;
 has_carry = false;
 if (digit > 9) 
 digit -= 10;
 has_carry = true;
 
 *d_first++ = digit;
 

 return std::make_tuple(d_first, has_carry);


template <typename InputIteratorLhs, typename InputIteratorRhs, typename OutputIterator>
OutputIterator digit_add(InputIteratorLhs lhs_first, InputIteratorLhs lhs_last,
 InputIteratorRhs rhs_first, InputIteratorRhs rhs_last,
 OutputIterator d_first) 
 bool has_carry = false;
 while (lhs_first != lhs_last && rhs_first != rhs_last) 
 auto sum = *lhs_first + *rhs_first;
 sum += has_carry;
 has_carry = false;
 if (sum > 9) 
 sum -= 10;
 has_carry = true;
 
 *d_first++ = sum;
 ++lhs_first;
 ++rhs_first;
 

 //only one of the following will run, the other will exit immediately
 std::tie(d_first, has_carry) = fill_rest(lhs_first, lhs_last, d_first, has_carry);
 std::tie(d_first, has_carry) = fill_rest(rhs_first, rhs_last, d_first, has_carry);
 if (has_carry) 
 *d_first++ = 1;
 

 return d_first;



Demo on Wandbox.



It is easy to see that verbosity and branching didn't decrease too much, and added usability does not compensate for it. I don't have the time to implement std::list solution, but I believe it will be shorter and less verbose.



Integrating custom linked list nodes into proposed algorithm



As algorithm requires only InputIterator and OutputIterator, it shouldn't be too hard to embed functionality into the node itself, and make some wrapper around it for OutputIterator.



Recursion



As @einpoklum already noted, it might be easier to implement this with recursion, and it will also lift a need to reverse the list later. Here is the rough sketch of the algorithm itself:



  1. If both elements are null and there is no carry, return


  2. Take the sum plus carry, being careful with nulls


  3. Raise the carry flag and decrease sum by 10 if it exceeds 9


  4. Go to 1, passing next list element of left, right, and output lists, and carry


  5. Write the sum into current output list element


This looks quite nice, and has a "flat" branching structure. Implementing this solution will require taking a risk of stackoverflow, but I don't think it is relevant in the question itself.






share|improve this answer




















  • Thanks @Incomputable for providing specific feedback on how to think about different algorithm implementations here. I am new to C++ 11 and the syntax of the proposed algorithm you've shared on Wanbox, but definitely will consider using your guidance to further optimize. Especially given I initially tried to solve this using recursion and find the use of a carry flag and subtraction interesting here.
    – greg
    Aug 17 at 20:26

















up vote
6
down vote














I'm mainly looking for any ways I can optimize my conditional
statements and arithmetic, my using statement, and use of pointers.




You can optimize your using statements by removing them. In this case simply prefixing the few occurrences with std:: would be the better solution.



What is this? 




 using std::ostream;



and this?




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



Remnants from an earlier version? Either way don't use the C headers. Instead use the C++ versions (cstddef [which you're already using!] and cstdlib) if you need those headers.

You're also missing <string>.



As far as I can tell the only reason this needs C++11 is to_string. If you get rid of that you can also drop the version requirement. However using modern C++ (11 and up) brings a lot of advantages in my opinion. As other people already pointed out you should use std::list and smart pointers.



On the topic of pointers, I see a bunch of news but not a single delete. So I'm guessing you are leaking memory. Check with valgrind to be sure.



Do you really need to use endl? In other words, do you really need to flush the buffer? I doubt it. Consider using n as an alternative. Also have a look at the C++ core guideline for endl.



The using statements in main are even more useless than the earlier ones.



As you don't depend on the return value you can drop return 0 from main as the compiler will generate it for you






share|improve this answer






















  • great suggestions, after a quick search valgrind seems very useful, thanks. My questions are: in place of endl would you suggest I use n? In what scenario should I flush the buffer? I'm using VS Code as my editor and the C++ 11 compile command from my original post, when I replace my usings with just #include <cstddef> #include <cstdlib> I get compile errors, is this expected or am I missing something?
    – greg
    Aug 17 at 19:45






  • 1




    (1) Sorry I forgot to mention n as the alternative, I'll edit it in. (2) Have a look at this regarding flush (3) VS Code is not a compiler but I assume you're using the Microsoft compiler? I am unable to make it work at all with the Microsoft compiler but it will work fine in Clang/GCC.
    – yuri
    Aug 17 at 20:02










  • No worries I will look into this, thanks! I'm using gcc (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609 Copyright (C) 2015 Free Software Foundation, Inc. through the Linux subsystem for Windows 10
    – greg
    Aug 17 at 20:28










  • Oh right, you even said so. My bad. I can make it work with GCC 5.4 however I am not using the Linux subsystem for W10 so I can't replicate your exact environment but afaik there is nothing needing those headers in your source code. What kind of errors are you getting? Did you try an online compiler to compare the output?
    – yuri
    Aug 17 at 20:34










  • They're mostly "was not declared in this scope" errors. Trying out Wandbox to showcase this here wandbox.org/permlink/kCpmFHwhLNeeYXVj
    – greg
    Aug 17 at 20:49

















up vote
5
down vote













Use std::vector<int> to store the numbers



Your post does contain




you are given two non-empty linked lists representing two non-negative integers.




It's not clear whether that is conceptual or more. If it is conceptual, I would strongly recommend using std::vector<int> to store the numbers.



If you do that, the code to construct the numbers gets really simple. As an example from proveDoubleCarry, the code to construct the two numbers can be 



std::vector<int> l19;
std::vector<int> l21, 9, 9, 9, 8, 9, 9;


instead of



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;


Get rid of the class Solution.



I don't see any need for the class. It does not provide any more abstractions that a simple function cannot provide. It can be replaced by a function



std::vector<int> addTwoNumbers(std::vector<int> const& l1,
 std::vector<int> const& l2);


Use recursive function to add the numbers



Implementation of addTwoNumbers becomes simple to understand by using a recursive helper function.



Here's how the two look in my implementation.



void addTwoNumbers(std::vector<int>::const_iterator iter1,
 std::vector<int>::const_iterator end1,
 std::vector<int>::const_iterator iter2,
 std::vector<int>::const_iterator end2,
 int carry,
 std::vector<int>& result)

 // Check for terminating condition.
 if ( iter1 == end1 && iter2 == end2 && carry == 0 )
 
 return;
 

 int sum = carry;
 if ( iter1 != end1 )
 
 sum += *iter1;
 
 if ( iter2 != end2 )
 
 sum += *iter2;
 

 carry = sum/10;
 sum = sum%10;

 result.push_back(sum);

 if ( iter1 != end1 )
 
 ++iter1;
 

 if ( iter2 != end2 )
 
 ++iter2;
 

 // Recurse
 addTwoNumbers(iter1, end1, iter2, end2, carry, result);


std::vector<int> addTwoNumbers(std::vector<int> const& l1,
 std::vector<int> const& l2)

 std::vector<int> result;
 addTwoNumbers(l1.begin(), l1.end(),
 l2.begin(), l2.end(),
 0,
 result);

 return result;



Print the input and output together



It is more useful to be able to see the input and the output together. Any errors in the code would be seen more easily when both of them are printed together. Example code would be



printNumber("First number", l1);
printNumber("Second number", l2);
printNumber("Result", result);


Here's a complete listing of my updated version of your program.



#include <iostream>
#include <vector>
#include <string>

void printNumber(std::vector<int>::const_reverse_iterator iter,
 std::vector<int>::const_reverse_iterator end)

 if ( iter == end )
 
 return;
 
 std::cout << *iter;
 printNumber(++iter, end);


void printNumber(std::string const& label,
 std::vector<int> const& num)

 std::cout << label << ": ( ";
 printNumber(num.rbegin(), num.rend());
 std::cout << " )n";


void addTwoNumbers(std::vector<int>::const_iterator iter1,
 std::vector<int>::const_iterator end1,
 std::vector<int>::const_iterator iter2,
 std::vector<int>::const_iterator end2,
 int carry,
 std::vector<int>& result)

 // Check for terminating condition.
 if ( iter1 == end1 && iter2 == end2 && carry == 0 )
 
 return;
 

 int sum = carry;
 if ( iter1 != end1 )
 
 sum += *iter1;
 
 if ( iter2 != end2 )
 
 sum += *iter2;
 

 carry = sum/10;
 sum = sum%10;

 result.push_back(sum);

 if ( iter1 != end1 )
 
 ++iter1;
 

 if ( iter2 != end2 )
 
 ++iter2;
 

 // Recurse
 addTwoNumbers(iter1, end1, iter2, end2, carry, result);


std::vector<int> addTwoNumbers(std::vector<int> const& l1,
 std::vector<int> const& l2)

 std::vector<int> result;
 addTwoNumbers(l1.begin(), l1.end(),
 l2.begin(), l2.end(),
 0,
 result);

 return result;



/**
 *
 * 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()

 std::cout << "nnBasic casen";

 std::vector<int> l12, 4, 3;
 std::vector<int> l25, 6, 4;

 auto result = addTwoNumbers(l1, l2);

 printNumber("First number", l1);
 printNumber("Second number", l2);
 printNumber("Result", result);


/**
 *
 * 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()

 std::cout << "nnUneven List sizesn";

 std::vector<int> l12, 4, 3;
 std::vector<int> l25, 6;

 auto result = addTwoNumbers(l1, l2);

 printNumber("First number", l1);
 printNumber("Second number", l2);
 printNumber("Result", result);


/**
 *
 * 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()

 std::cout << "nnDouble Carryn";

 std::vector<int> l19;
 std::vector<int> l21, 9, 9, 9, 8, 9, 9;

 auto result = addTwoNumbers(l1, l2);

 printNumber("First number", l1);
 printNumber("Second number", l2);
 printNumber("Result", result);


int main()

 std::cout << "Mr Robot is running prgm..." << std::endl;

 proveBasicCase();
 proveListSizeNotEqual();
 proveDoubleCarry();

 return 0;



and its output



Mr Robot is running prgm...


Basic case
First number: ( 342 )
Second number: ( 465 )
Result: ( 807 )


Uneven List sizes
First number: ( 342 )
Second number: ( 65 )
Result: ( 407 )


Double Carry
First number: ( 9 )
Second number: ( 9989991 )
Result: ( 9990000 )





share|improve this answer





























    up vote
    4
    down vote













    Your Solution::addTwoNumbers routine leaks 3 list nodes per call. In the initializing part:



     ListNode *node = new ListNode(0); // <-- the only used
     ListNode *currentNode = new ListNode(0);
     currentNode = node;

     ListNode *currentL1 = new ListNode(0);
     ListNode *currentL2 = new ListNode(0);
     currentL1 = l1;
     currentL2 = l2;


    all allocated nodes except the first one are abandoned: you allocate them, but you never use or delete them.
    Do appropriate initializataion instead:



     ListNode *node = new ListNode(0);
     ListNode *currentNode = node;

     ListNode *currentL1 = l1;
     ListNode *currentL2 = l2;





    share|improve this answer






















    • Great point, I anticipated some memory error and appreciate the code example given to resolve it. will implement once I refactor. Thanks!
      – greg
      Aug 20 at 16:22










    Your Answer




    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ifUsing("editor", function ()
    StackExchange.using("externalEditor", function ()
    StackExchange.using("snippets", function ()
    StackExchange.snippets.init();
    );
    );
    , "code-snippets");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "196"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    convertImagesToLinks: false,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );













     

    draft saved


    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f201902%2fadd-two-numbers-given-in-reverse-order-from-a-linked-list%23new-answer', 'question_page');

    );

    Post as a guest

















    5 Answers
    5






    active

    oldest

    votes








    5 Answers
    5






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    7
    down vote



    accepted










    Don't write your own container classes when there's no need



    The problem you describe involves working with lists, not implementing a list data structure. Use a ready-made list from the standard library - std::list should be fine. So, essentially you need to implement the following function:



    using digit_t = uint8_t; // or unsigned char if you like
    using num_in_list_t = std::list<digit_t>;

    num_in_list_t add(const num_in_list_t& l1, const num_in_list_t& l2);


    Mark const where relevant



    Your addTwoNumbers() function takes non-const ListNode *s. This suggests you may intend to change the pointed-to data - which you do not.



    Don't implement your own pretty-printer



    You can use Louis Delacroix's effective cxx pretty printer; it might not do exactly what you want, but again - why make your life difficult for no reason?



    Follow best practices for memory management



    With modern C++, you should:



    • Avoid using new and delete directly

    • Avoid using raw pointers which own the pointed-to data

    Instead, use smart pointers; specifically, allocate with std::make_unique (C++14), to get an allocation which will be released automatically and never leak. Of course - if you used std::list, you wouldn't have to allocate anything anyway.



    More on this in C++ Core guidelines Section R: See guidelines R.10, R.11, R.20, R.21, R.23.



    Don't rush to optimize



    The question is about correctness and elegance, not performance (or at least - it should be). You should only care about minizing the time (and space) complexity should be, and not going over that - and indeed, you have kept your implementation to O(1) extra space and O(|l1|+|l2|) time. That's enough.



    De-spaghetti-ize your main loop



    Your main loop code is a bit long, and could be made clearer with a bit of work. At the very least you should add comments, but a better alternative would be to change the code to be more self-documenting.



    Don't be afraid of recursion



    It's often easier to solve problems on linearly-iterable data recursively - doing something with the head, doing something with the tail, and finishing up if need be. This is also the case for you, except that the recursive case can involve an advance in either one list or the other.






    share|improve this answer


















    • 1




      Thanks a lot, this explanation is very clear and helpful. only questions I have are how did you compute the space complexity and can you give some more guidance on how to make the code more self documenting / de-spaghetti-ize it?
      – greg
      Aug 17 at 19:28






    • 1




      @GregDegruy: Start by following the rest of the advice; post it as a new question here; and post a comment here with a link to it.
      – einpoklum
      Aug 18 at 7:28






    • 2




      @GregDegruy: Also, if you follow my "don't be afraid of recursion" advice, you should get nice, clean, short code.
      – einpoklum
      Aug 18 at 8:25














    up vote
    7
    down vote



    accepted










    Don't write your own container classes when there's no need



    The problem you describe involves working with lists, not implementing a list data structure. Use a ready-made list from the standard library - std::list should be fine. So, essentially you need to implement the following function:



    using digit_t = uint8_t; // or unsigned char if you like
    using num_in_list_t = std::list<digit_t>;

    num_in_list_t add(const num_in_list_t& l1, const num_in_list_t& l2);


    Mark const where relevant



    Your addTwoNumbers() function takes non-const ListNode *s. This suggests you may intend to change the pointed-to data - which you do not.



    Don't implement your own pretty-printer



    You can use Louis Delacroix's effective cxx pretty printer; it might not do exactly what you want, but again - why make your life difficult for no reason?



    Follow best practices for memory management



    With modern C++, you should:



    • Avoid using new and delete directly

    • Avoid using raw pointers which own the pointed-to data

    Instead, use smart pointers; specifically, allocate with std::make_unique (C++14), to get an allocation which will be released automatically and never leak. Of course - if you used std::list, you wouldn't have to allocate anything anyway.



    More on this in C++ Core guidelines Section R: See guidelines R.10, R.11, R.20, R.21, R.23.



    Don't rush to optimize



    The question is about correctness and elegance, not performance (or at least - it should be). You should only care about minizing the time (and space) complexity should be, and not going over that - and indeed, you have kept your implementation to O(1) extra space and O(|l1|+|l2|) time. That's enough.



    De-spaghetti-ize your main loop



    Your main loop code is a bit long, and could be made clearer with a bit of work. At the very least you should add comments, but a better alternative would be to change the code to be more self-documenting.



    Don't be afraid of recursion



    It's often easier to solve problems on linearly-iterable data recursively - doing something with the head, doing something with the tail, and finishing up if need be. This is also the case for you, except that the recursive case can involve an advance in either one list or the other.






    share|improve this answer


















    • 1




      Thanks a lot, this explanation is very clear and helpful. only questions I have are how did you compute the space complexity and can you give some more guidance on how to make the code more self documenting / de-spaghetti-ize it?
      – greg
      Aug 17 at 19:28






    • 1




      @GregDegruy: Start by following the rest of the advice; post it as a new question here; and post a comment here with a link to it.
      – einpoklum
      Aug 18 at 7:28






    • 2




      @GregDegruy: Also, if you follow my "don't be afraid of recursion" advice, you should get nice, clean, short code.
      – einpoklum
      Aug 18 at 8:25












    up vote
    7
    down vote



    accepted







    up vote
    7
    down vote



    accepted






    Don't write your own container classes when there's no need



    The problem you describe involves working with lists, not implementing a list data structure. Use a ready-made list from the standard library - std::list should be fine. So, essentially you need to implement the following function:



    using digit_t = uint8_t; // or unsigned char if you like
    using num_in_list_t = std::list<digit_t>;

    num_in_list_t add(const num_in_list_t& l1, const num_in_list_t& l2);


    Mark const where relevant



    Your addTwoNumbers() function takes non-const ListNode *s. This suggests you may intend to change the pointed-to data - which you do not.



    Don't implement your own pretty-printer



    You can use Louis Delacroix's effective cxx pretty printer; it might not do exactly what you want, but again - why make your life difficult for no reason?



    Follow best practices for memory management



    With modern C++, you should:



    • Avoid using new and delete directly

    • Avoid using raw pointers which own the pointed-to data

    Instead, use smart pointers; specifically, allocate with std::make_unique (C++14), to get an allocation which will be released automatically and never leak. Of course - if you used std::list, you wouldn't have to allocate anything anyway.



    More on this in C++ Core guidelines Section R: See guidelines R.10, R.11, R.20, R.21, R.23.



    Don't rush to optimize



    The question is about correctness and elegance, not performance (or at least - it should be). You should only care about minizing the time (and space) complexity should be, and not going over that - and indeed, you have kept your implementation to O(1) extra space and O(|l1|+|l2|) time. That's enough.



    De-spaghetti-ize your main loop



    Your main loop code is a bit long, and could be made clearer with a bit of work. At the very least you should add comments, but a better alternative would be to change the code to be more self-documenting.



    Don't be afraid of recursion



    It's often easier to solve problems on linearly-iterable data recursively - doing something with the head, doing something with the tail, and finishing up if need be. This is also the case for you, except that the recursive case can involve an advance in either one list or the other.






    share|improve this answer














    Don't write your own container classes when there's no need



    The problem you describe involves working with lists, not implementing a list data structure. Use a ready-made list from the standard library - std::list should be fine. So, essentially you need to implement the following function:



    using digit_t = uint8_t; // or unsigned char if you like
    using num_in_list_t = std::list<digit_t>;

    num_in_list_t add(const num_in_list_t& l1, const num_in_list_t& l2);


    Mark const where relevant



    Your addTwoNumbers() function takes non-const ListNode *s. This suggests you may intend to change the pointed-to data - which you do not.



    Don't implement your own pretty-printer



    You can use Louis Delacroix's effective cxx pretty printer; it might not do exactly what you want, but again - why make your life difficult for no reason?



    Follow best practices for memory management



    With modern C++, you should:



    • Avoid using new and delete directly

    • Avoid using raw pointers which own the pointed-to data

    Instead, use smart pointers; specifically, allocate with std::make_unique (C++14), to get an allocation which will be released automatically and never leak. Of course - if you used std::list, you wouldn't have to allocate anything anyway.



    More on this in C++ Core guidelines Section R: See guidelines R.10, R.11, R.20, R.21, R.23.



    Don't rush to optimize



    The question is about correctness and elegance, not performance (or at least - it should be). You should only care about minizing the time (and space) complexity should be, and not going over that - and indeed, you have kept your implementation to O(1) extra space and O(|l1|+|l2|) time. That's enough.



    De-spaghetti-ize your main loop



    Your main loop code is a bit long, and could be made clearer with a bit of work. At the very least you should add comments, but a better alternative would be to change the code to be more self-documenting.



    Don't be afraid of recursion



    It's often easier to solve problems on linearly-iterable data recursively - doing something with the head, doing something with the tail, and finishing up if need be. This is also the case for you, except that the recursive case can involve an advance in either one list or the other.







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited Aug 18 at 7:29

























    answered Aug 17 at 19:01









    einpoklum

    1,038417




    1,038417







    • 1




      Thanks a lot, this explanation is very clear and helpful. only questions I have are how did you compute the space complexity and can you give some more guidance on how to make the code more self documenting / de-spaghetti-ize it?
      – greg
      Aug 17 at 19:28






    • 1




      @GregDegruy: Start by following the rest of the advice; post it as a new question here; and post a comment here with a link to it.
      – einpoklum
      Aug 18 at 7:28






    • 2




      @GregDegruy: Also, if you follow my "don't be afraid of recursion" advice, you should get nice, clean, short code.
      – einpoklum
      Aug 18 at 8:25












    • 1




      Thanks a lot, this explanation is very clear and helpful. only questions I have are how did you compute the space complexity and can you give some more guidance on how to make the code more self documenting / de-spaghetti-ize it?
      – greg
      Aug 17 at 19:28






    • 1




      @GregDegruy: Start by following the rest of the advice; post it as a new question here; and post a comment here with a link to it.
      – einpoklum
      Aug 18 at 7:28






    • 2




      @GregDegruy: Also, if you follow my "don't be afraid of recursion" advice, you should get nice, clean, short code.
      – einpoklum
      Aug 18 at 8:25







    1




    1




    Thanks a lot, this explanation is very clear and helpful. only questions I have are how did you compute the space complexity and can you give some more guidance on how to make the code more self documenting / de-spaghetti-ize it?
    – greg
    Aug 17 at 19:28




    Thanks a lot, this explanation is very clear and helpful. only questions I have are how did you compute the space complexity and can you give some more guidance on how to make the code more self documenting / de-spaghetti-ize it?
    – greg
    Aug 17 at 19:28




    1




    1




    @GregDegruy: Start by following the rest of the advice; post it as a new question here; and post a comment here with a link to it.
    – einpoklum
    Aug 18 at 7:28




    @GregDegruy: Start by following the rest of the advice; post it as a new question here; and post a comment here with a link to it.
    – einpoklum
    Aug 18 at 7:28




    2




    2




    @GregDegruy: Also, if you follow my "don't be afraid of recursion" advice, you should get nice, clean, short code.
    – einpoklum
    Aug 18 at 8:25




    @GregDegruy: Also, if you follow my "don't be afraid of recursion" advice, you should get nice, clean, short code.
    – einpoklum
    Aug 18 at 8:25












    up vote
    6
    down vote













    As @einpoklum already went into reusing existing code, I'll dive deeper into the algorithm used.



    Current algorithm



    Until the end of both lists reached:



    1. Get a sum, taking into account if one of them is null


    2. Assign the sum to current node, raising carry flag through branching


    3. ...


    And that's as much as I could dive into it, since it became too hard to deal with branching and parts of code being in different places.



    Proposed algorithm



    Let me show the algorithm I would implement:



    Until either end is reached:



    1. Take the sum plus the carry


    2. If sum is greater than 9, substract 10 and raise the carry flag


    3. Advance lists by one, including the output list


    When either end is reached, just bump the remaining one, taking carry into account. Reverse the resulting list, to finish the last requirement.



    Implementation of proposed algorithm



    Standard library evangelist might march on with iterator support, but then will be disappointed:



    template <typename InputIterator, typename OutputIterator>
    auto fill_rest(InputIterator first, InputIterator last, 
     OutputIterator d_first, bool has_carry) 
     for (; first != last; ++first) 
     auto digit = *first;
     digit += has_carry;
     has_carry = false;
     if (digit > 9) 
     digit -= 10;
     has_carry = true;
     
     *d_first++ = digit;
     

     return std::make_tuple(d_first, has_carry);


    template <typename InputIteratorLhs, typename InputIteratorRhs, typename OutputIterator>
    OutputIterator digit_add(InputIteratorLhs lhs_first, InputIteratorLhs lhs_last,
     InputIteratorRhs rhs_first, InputIteratorRhs rhs_last,
     OutputIterator d_first) 
     bool has_carry = false;
     while (lhs_first != lhs_last && rhs_first != rhs_last) 
     auto sum = *lhs_first + *rhs_first;
     sum += has_carry;
     has_carry = false;
     if (sum > 9) 
     sum -= 10;
     has_carry = true;
     
     *d_first++ = sum;
     ++lhs_first;
     ++rhs_first;
     

     //only one of the following will run, the other will exit immediately
     std::tie(d_first, has_carry) = fill_rest(lhs_first, lhs_last, d_first, has_carry);
     std::tie(d_first, has_carry) = fill_rest(rhs_first, rhs_last, d_first, has_carry);
     if (has_carry) 
     *d_first++ = 1;
     

     return d_first;



    Demo on Wandbox.



    It is easy to see that verbosity and branching didn't decrease too much, and added usability does not compensate for it. I don't have the time to implement std::list solution, but I believe it will be shorter and less verbose.



    Integrating custom linked list nodes into proposed algorithm



    As algorithm requires only InputIterator and OutputIterator, it shouldn't be too hard to embed functionality into the node itself, and make some wrapper around it for OutputIterator.



    Recursion



    As @einpoklum already noted, it might be easier to implement this with recursion, and it will also lift a need to reverse the list later. Here is the rough sketch of the algorithm itself:



    1. If both elements are null and there is no carry, return


    2. Take the sum plus carry, being careful with nulls


    3. Raise the carry flag and decrease sum by 10 if it exceeds 9


    4. Go to 1, passing next list element of left, right, and output lists, and carry


    5. Write the sum into current output list element


    This looks quite nice, and has a "flat" branching structure. Implementing this solution will require taking a risk of stackoverflow, but I don't think it is relevant in the question itself.






    share|improve this answer




















    • Thanks @Incomputable for providing specific feedback on how to think about different algorithm implementations here. I am new to C++ 11 and the syntax of the proposed algorithm you've shared on Wanbox, but definitely will consider using your guidance to further optimize. Especially given I initially tried to solve this using recursion and find the use of a carry flag and subtraction interesting here.
      – greg
      Aug 17 at 20:26














    up vote
    6
    down vote













    As @einpoklum already went into reusing existing code, I'll dive deeper into the algorithm used.



    Current algorithm



    Until the end of both lists reached:



    1. Get a sum, taking into account if one of them is null


    2. Assign the sum to current node, raising carry flag through branching


    3. ...


    And that's as much as I could dive into it, since it became too hard to deal with branching and parts of code being in different places.



    Proposed algorithm



    Let me show the algorithm I would implement:



    Until either end is reached:



    1. Take the sum plus the carry


    2. If sum is greater than 9, substract 10 and raise the carry flag


    3. Advance lists by one, including the output list


    When either end is reached, just bump the remaining one, taking carry into account. Reverse the resulting list, to finish the last requirement.



    Implementation of proposed algorithm



    Standard library evangelist might march on with iterator support, but then will be disappointed:



    template <typename InputIterator, typename OutputIterator>
    auto fill_rest(InputIterator first, InputIterator last, 
     OutputIterator d_first, bool has_carry) 
     for (; first != last; ++first) 
     auto digit = *first;
     digit += has_carry;
     has_carry = false;
     if (digit > 9) 
     digit -= 10;
     has_carry = true;
     
     *d_first++ = digit;
     

     return std::make_tuple(d_first, has_carry);


    template <typename InputIteratorLhs, typename InputIteratorRhs, typename OutputIterator>
    OutputIterator digit_add(InputIteratorLhs lhs_first, InputIteratorLhs lhs_last,
     InputIteratorRhs rhs_first, InputIteratorRhs rhs_last,
     OutputIterator d_first) 
     bool has_carry = false;
     while (lhs_first != lhs_last && rhs_first != rhs_last) 
     auto sum = *lhs_first + *rhs_first;
     sum += has_carry;
     has_carry = false;
     if (sum > 9) 
     sum -= 10;
     has_carry = true;
     
     *d_first++ = sum;
     ++lhs_first;
     ++rhs_first;
     

     //only one of the following will run, the other will exit immediately
     std::tie(d_first, has_carry) = fill_rest(lhs_first, lhs_last, d_first, has_carry);
     std::tie(d_first, has_carry) = fill_rest(rhs_first, rhs_last, d_first, has_carry);
     if (has_carry) 
     *d_first++ = 1;
     

     return d_first;



    Demo on Wandbox.



    It is easy to see that verbosity and branching didn't decrease too much, and added usability does not compensate for it. I don't have the time to implement std::list solution, but I believe it will be shorter and less verbose.



    Integrating custom linked list nodes into proposed algorithm



    As algorithm requires only InputIterator and OutputIterator, it shouldn't be too hard to embed functionality into the node itself, and make some wrapper around it for OutputIterator.



    Recursion



    As @einpoklum already noted, it might be easier to implement this with recursion, and it will also lift a need to reverse the list later. Here is the rough sketch of the algorithm itself:



    1. If both elements are null and there is no carry, return


    2. Take the sum plus carry, being careful with nulls


    3. Raise the carry flag and decrease sum by 10 if it exceeds 9


    4. Go to 1, passing next list element of left, right, and output lists, and carry


    5. Write the sum into current output list element


    This looks quite nice, and has a "flat" branching structure. Implementing this solution will require taking a risk of stackoverflow, but I don't think it is relevant in the question itself.






    share|improve this answer




















    • Thanks @Incomputable for providing specific feedback on how to think about different algorithm implementations here. I am new to C++ 11 and the syntax of the proposed algorithm you've shared on Wanbox, but definitely will consider using your guidance to further optimize. Especially given I initially tried to solve this using recursion and find the use of a carry flag and subtraction interesting here.
      – greg
      Aug 17 at 20:26












    up vote
    6
    down vote










    up vote
    6
    down vote









    As @einpoklum already went into reusing existing code, I'll dive deeper into the algorithm used.



    Current algorithm



    Until the end of both lists reached:



    1. Get a sum, taking into account if one of them is null


    2. Assign the sum to current node, raising carry flag through branching


    3. ...


    And that's as much as I could dive into it, since it became too hard to deal with branching and parts of code being in different places.



    Proposed algorithm



    Let me show the algorithm I would implement:



    Until either end is reached:



    1. Take the sum plus the carry


    2. If sum is greater than 9, substract 10 and raise the carry flag


    3. Advance lists by one, including the output list


    When either end is reached, just bump the remaining one, taking carry into account. Reverse the resulting list, to finish the last requirement.



    Implementation of proposed algorithm



    Standard library evangelist might march on with iterator support, but then will be disappointed:



    template <typename InputIterator, typename OutputIterator>
    auto fill_rest(InputIterator first, InputIterator last, 
     OutputIterator d_first, bool has_carry) 
     for (; first != last; ++first) 
     auto digit = *first;
     digit += has_carry;
     has_carry = false;
     if (digit > 9) 
     digit -= 10;
     has_carry = true;
     
     *d_first++ = digit;
     

     return std::make_tuple(d_first, has_carry);


    template <typename InputIteratorLhs, typename InputIteratorRhs, typename OutputIterator>
    OutputIterator digit_add(InputIteratorLhs lhs_first, InputIteratorLhs lhs_last,
     InputIteratorRhs rhs_first, InputIteratorRhs rhs_last,
     OutputIterator d_first) 
     bool has_carry = false;
     while (lhs_first != lhs_last && rhs_first != rhs_last) 
     auto sum = *lhs_first + *rhs_first;
     sum += has_carry;
     has_carry = false;
     if (sum > 9) 
     sum -= 10;
     has_carry = true;
     
     *d_first++ = sum;
     ++lhs_first;
     ++rhs_first;
     

     //only one of the following will run, the other will exit immediately
     std::tie(d_first, has_carry) = fill_rest(lhs_first, lhs_last, d_first, has_carry);
     std::tie(d_first, has_carry) = fill_rest(rhs_first, rhs_last, d_first, has_carry);
     if (has_carry) 
     *d_first++ = 1;
     

     return d_first;



    Demo on Wandbox.



    It is easy to see that verbosity and branching didn't decrease too much, and added usability does not compensate for it. I don't have the time to implement std::list solution, but I believe it will be shorter and less verbose.



    Integrating custom linked list nodes into proposed algorithm



    As algorithm requires only InputIterator and OutputIterator, it shouldn't be too hard to embed functionality into the node itself, and make some wrapper around it for OutputIterator.



    Recursion



    As @einpoklum already noted, it might be easier to implement this with recursion, and it will also lift a need to reverse the list later. Here is the rough sketch of the algorithm itself:



    1. If both elements are null and there is no carry, return


    2. Take the sum plus carry, being careful with nulls


    3. Raise the carry flag and decrease sum by 10 if it exceeds 9


    4. Go to 1, passing next list element of left, right, and output lists, and carry


    5. Write the sum into current output list element


    This looks quite nice, and has a "flat" branching structure. Implementing this solution will require taking a risk of stackoverflow, but I don't think it is relevant in the question itself.






    share|improve this answer












    As @einpoklum already went into reusing existing code, I'll dive deeper into the algorithm used.



    Current algorithm



    Until the end of both lists reached:



    1. Get a sum, taking into account if one of them is null


    2. Assign the sum to current node, raising carry flag through branching


    3. ...


    And that's as much as I could dive into it, since it became too hard to deal with branching and parts of code being in different places.



    Proposed algorithm



    Let me show the algorithm I would implement:



    Until either end is reached:



    1. Take the sum plus the carry


    2. If sum is greater than 9, substract 10 and raise the carry flag


    3. Advance lists by one, including the output list


    When either end is reached, just bump the remaining one, taking carry into account. Reverse the resulting list, to finish the last requirement.



    Implementation of proposed algorithm



    Standard library evangelist might march on with iterator support, but then will be disappointed:



    template <typename InputIterator, typename OutputIterator>
    auto fill_rest(InputIterator first, InputIterator last, 
     OutputIterator d_first, bool has_carry) 
     for (; first != last; ++first) 
     auto digit = *first;
     digit += has_carry;
     has_carry = false;
     if (digit > 9) 
     digit -= 10;
     has_carry = true;
     
     *d_first++ = digit;
     

     return std::make_tuple(d_first, has_carry);


    template <typename InputIteratorLhs, typename InputIteratorRhs, typename OutputIterator>
    OutputIterator digit_add(InputIteratorLhs lhs_first, InputIteratorLhs lhs_last,
     InputIteratorRhs rhs_first, InputIteratorRhs rhs_last,
     OutputIterator d_first) 
     bool has_carry = false;
     while (lhs_first != lhs_last && rhs_first != rhs_last) 
     auto sum = *lhs_first + *rhs_first;
     sum += has_carry;
     has_carry = false;
     if (sum > 9) 
     sum -= 10;
     has_carry = true;
     
     *d_first++ = sum;
     ++lhs_first;
     ++rhs_first;
     

     //only one of the following will run, the other will exit immediately
     std::tie(d_first, has_carry) = fill_rest(lhs_first, lhs_last, d_first, has_carry);
     std::tie(d_first, has_carry) = fill_rest(rhs_first, rhs_last, d_first, has_carry);
     if (has_carry) 
     *d_first++ = 1;
     

     return d_first;



    Demo on Wandbox.



    It is easy to see that verbosity and branching didn't decrease too much, and added usability does not compensate for it. I don't have the time to implement std::list solution, but I believe it will be shorter and less verbose.



    Integrating custom linked list nodes into proposed algorithm



    As algorithm requires only InputIterator and OutputIterator, it shouldn't be too hard to embed functionality into the node itself, and make some wrapper around it for OutputIterator.



    Recursion



    As @einpoklum already noted, it might be easier to implement this with recursion, and it will also lift a need to reverse the list later. Here is the rough sketch of the algorithm itself:



    1. If both elements are null and there is no carry, return


    2. Take the sum plus carry, being careful with nulls


    3. Raise the carry flag and decrease sum by 10 if it exceeds 9


    4. Go to 1, passing next list element of left, right, and output lists, and carry


    5. Write the sum into current output list element


    This looks quite nice, and has a "flat" branching structure. Implementing this solution will require taking a risk of stackoverflow, but I don't think it is relevant in the question itself.







    share|improve this answer












    share|improve this answer



    share|improve this answer










    answered Aug 17 at 19:41









    Incomputable

    6,11421347




    6,11421347











    • Thanks @Incomputable for providing specific feedback on how to think about different algorithm implementations here. I am new to C++ 11 and the syntax of the proposed algorithm you've shared on Wanbox, but definitely will consider using your guidance to further optimize. Especially given I initially tried to solve this using recursion and find the use of a carry flag and subtraction interesting here.
      – greg
      Aug 17 at 20:26
















    • Thanks @Incomputable for providing specific feedback on how to think about different algorithm implementations here. I am new to C++ 11 and the syntax of the proposed algorithm you've shared on Wanbox, but definitely will consider using your guidance to further optimize. Especially given I initially tried to solve this using recursion and find the use of a carry flag and subtraction interesting here.
      – greg
      Aug 17 at 20:26















    Thanks @Incomputable for providing specific feedback on how to think about different algorithm implementations here. I am new to C++ 11 and the syntax of the proposed algorithm you've shared on Wanbox, but definitely will consider using your guidance to further optimize. Especially given I initially tried to solve this using recursion and find the use of a carry flag and subtraction interesting here.
    – greg
    Aug 17 at 20:26




    Thanks @Incomputable for providing specific feedback on how to think about different algorithm implementations here. I am new to C++ 11 and the syntax of the proposed algorithm you've shared on Wanbox, but definitely will consider using your guidance to further optimize. Especially given I initially tried to solve this using recursion and find the use of a carry flag and subtraction interesting here.
    – greg
    Aug 17 at 20:26










    up vote
    6
    down vote














    I'm mainly looking for any ways I can optimize my conditional
    statements and arithmetic, my using statement, and use of pointers.




    You can optimize your using statements by removing them. In this case simply prefixing the few occurrences with std:: would be the better solution.



    What is this? 




     using std::ostream;



    and this?




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



    Remnants from an earlier version? Either way don't use the C headers. Instead use the C++ versions (cstddef [which you're already using!] and cstdlib) if you need those headers.

    You're also missing <string>.



    As far as I can tell the only reason this needs C++11 is to_string. If you get rid of that you can also drop the version requirement. However using modern C++ (11 and up) brings a lot of advantages in my opinion. As other people already pointed out you should use std::list and smart pointers.



    On the topic of pointers, I see a bunch of news but not a single delete. So I'm guessing you are leaking memory. Check with valgrind to be sure.



    Do you really need to use endl? In other words, do you really need to flush the buffer? I doubt it. Consider using n as an alternative. Also have a look at the C++ core guideline for endl.



    The using statements in main are even more useless than the earlier ones.



    As you don't depend on the return value you can drop return 0 from main as the compiler will generate it for you






    share|improve this answer






















    • great suggestions, after a quick search valgrind seems very useful, thanks. My questions are: in place of endl would you suggest I use n? In what scenario should I flush the buffer? I'm using VS Code as my editor and the C++ 11 compile command from my original post, when I replace my usings with just #include <cstddef> #include <cstdlib> I get compile errors, is this expected or am I missing something?
      – greg
      Aug 17 at 19:45






    • 1




      (1) Sorry I forgot to mention n as the alternative, I'll edit it in. (2) Have a look at this regarding flush (3) VS Code is not a compiler but I assume you're using the Microsoft compiler? I am unable to make it work at all with the Microsoft compiler but it will work fine in Clang/GCC.
      – yuri
      Aug 17 at 20:02










    • No worries I will look into this, thanks! I'm using gcc (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609 Copyright (C) 2015 Free Software Foundation, Inc. through the Linux subsystem for Windows 10
      – greg
      Aug 17 at 20:28










    • Oh right, you even said so. My bad. I can make it work with GCC 5.4 however I am not using the Linux subsystem for W10 so I can't replicate your exact environment but afaik there is nothing needing those headers in your source code. What kind of errors are you getting? Did you try an online compiler to compare the output?
      – yuri
      Aug 17 at 20:34










    • They're mostly "was not declared in this scope" errors. Trying out Wandbox to showcase this here wandbox.org/permlink/kCpmFHwhLNeeYXVj
      – greg
      Aug 17 at 20:49














    up vote
    6
    down vote














    I'm mainly looking for any ways I can optimize my conditional
    statements and arithmetic, my using statement, and use of pointers.




    You can optimize your using statements by removing them. In this case simply prefixing the few occurrences with std:: would be the better solution.



    What is this? 




     using std::ostream;



    and this?




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



    Remnants from an earlier version? Either way don't use the C headers. Instead use the C++ versions (cstddef [which you're already using!] and cstdlib) if you need those headers.

    You're also missing <string>.



    As far as I can tell the only reason this needs C++11 is to_string. If you get rid of that you can also drop the version requirement. However using modern C++ (11 and up) brings a lot of advantages in my opinion. As other people already pointed out you should use std::list and smart pointers.



    On the topic of pointers, I see a bunch of news but not a single delete. So I'm guessing you are leaking memory. Check with valgrind to be sure.



    Do you really need to use endl? In other words, do you really need to flush the buffer? I doubt it. Consider using n as an alternative. Also have a look at the C++ core guideline for endl.



    The using statements in main are even more useless than the earlier ones.



    As you don't depend on the return value you can drop return 0 from main as the compiler will generate it for you






    share|improve this answer






















    • great suggestions, after a quick search valgrind seems very useful, thanks. My questions are: in place of endl would you suggest I use n? In what scenario should I flush the buffer? I'm using VS Code as my editor and the C++ 11 compile command from my original post, when I replace my usings with just #include <cstddef> #include <cstdlib> I get compile errors, is this expected or am I missing something?
      – greg
      Aug 17 at 19:45






    • 1




      (1) Sorry I forgot to mention n as the alternative, I'll edit it in. (2) Have a look at this regarding flush (3) VS Code is not a compiler but I assume you're using the Microsoft compiler? I am unable to make it work at all with the Microsoft compiler but it will work fine in Clang/GCC.
      – yuri
      Aug 17 at 20:02










    • No worries I will look into this, thanks! I'm using gcc (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609 Copyright (C) 2015 Free Software Foundation, Inc. through the Linux subsystem for Windows 10
      – greg
      Aug 17 at 20:28










    • Oh right, you even said so. My bad. I can make it work with GCC 5.4 however I am not using the Linux subsystem for W10 so I can't replicate your exact environment but afaik there is nothing needing those headers in your source code. What kind of errors are you getting? Did you try an online compiler to compare the output?
      – yuri
      Aug 17 at 20:34










    • They're mostly "was not declared in this scope" errors. Trying out Wandbox to showcase this here wandbox.org/permlink/kCpmFHwhLNeeYXVj
      – greg
      Aug 17 at 20:49












    up vote
    6
    down vote










    up vote
    6
    down vote










    I'm mainly looking for any ways I can optimize my conditional
    statements and arithmetic, my using statement, and use of pointers.




    You can optimize your using statements by removing them. In this case simply prefixing the few occurrences with std:: would be the better solution.



    What is this? 




     using std::ostream;



    and this?




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



    Remnants from an earlier version? Either way don't use the C headers. Instead use the C++ versions (cstddef [which you're already using!] and cstdlib) if you need those headers.

    You're also missing <string>.



    As far as I can tell the only reason this needs C++11 is to_string. If you get rid of that you can also drop the version requirement. However using modern C++ (11 and up) brings a lot of advantages in my opinion. As other people already pointed out you should use std::list and smart pointers.



    On the topic of pointers, I see a bunch of news but not a single delete. So I'm guessing you are leaking memory. Check with valgrind to be sure.



    Do you really need to use endl? In other words, do you really need to flush the buffer? I doubt it. Consider using n as an alternative. Also have a look at the C++ core guideline for endl.



    The using statements in main are even more useless than the earlier ones.



    As you don't depend on the return value you can drop return 0 from main as the compiler will generate it for you






    share|improve this answer















    I'm mainly looking for any ways I can optimize my conditional
    statements and arithmetic, my using statement, and use of pointers.




    You can optimize your using statements by removing them. In this case simply prefixing the few occurrences with std:: would be the better solution.



    What is this? 




     using std::ostream;



    and this?




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



    Remnants from an earlier version? Either way don't use the C headers. Instead use the C++ versions (cstddef [which you're already using!] and cstdlib) if you need those headers.

    You're also missing <string>.



    As far as I can tell the only reason this needs C++11 is to_string. If you get rid of that you can also drop the version requirement. However using modern C++ (11 and up) brings a lot of advantages in my opinion. As other people already pointed out you should use std::list and smart pointers.



    On the topic of pointers, I see a bunch of news but not a single delete. So I'm guessing you are leaking memory. Check with valgrind to be sure.



    Do you really need to use endl? In other words, do you really need to flush the buffer? I doubt it. Consider using n as an alternative. Also have a look at the C++ core guideline for endl.



    The using statements in main are even more useless than the earlier ones.



    As you don't depend on the return value you can drop return 0 from main as the compiler will generate it for you







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited Aug 18 at 6:59

























    answered Aug 17 at 19:22









    yuri

    3,47521033




    3,47521033











    • great suggestions, after a quick search valgrind seems very useful, thanks. My questions are: in place of endl would you suggest I use n? In what scenario should I flush the buffer? I'm using VS Code as my editor and the C++ 11 compile command from my original post, when I replace my usings with just #include <cstddef> #include <cstdlib> I get compile errors, is this expected or am I missing something?
      – greg
      Aug 17 at 19:45






    • 1




      (1) Sorry I forgot to mention n as the alternative, I'll edit it in. (2) Have a look at this regarding flush (3) VS Code is not a compiler but I assume you're using the Microsoft compiler? I am unable to make it work at all with the Microsoft compiler but it will work fine in Clang/GCC.
      – yuri
      Aug 17 at 20:02










    • No worries I will look into this, thanks! I'm using gcc (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609 Copyright (C) 2015 Free Software Foundation, Inc. through the Linux subsystem for Windows 10
      – greg
      Aug 17 at 20:28










    • Oh right, you even said so. My bad. I can make it work with GCC 5.4 however I am not using the Linux subsystem for W10 so I can't replicate your exact environment but afaik there is nothing needing those headers in your source code. What kind of errors are you getting? Did you try an online compiler to compare the output?
      – yuri
      Aug 17 at 20:34










    • They're mostly "was not declared in this scope" errors. Trying out Wandbox to showcase this here wandbox.org/permlink/kCpmFHwhLNeeYXVj
      – greg
      Aug 17 at 20:49
















    • great suggestions, after a quick search valgrind seems very useful, thanks. My questions are: in place of endl would you suggest I use n? In what scenario should I flush the buffer? I'm using VS Code as my editor and the C++ 11 compile command from my original post, when I replace my usings with just #include <cstddef> #include <cstdlib> I get compile errors, is this expected or am I missing something?
      – greg
      Aug 17 at 19:45






    • 1




      (1) Sorry I forgot to mention n as the alternative, I'll edit it in. (2) Have a look at this regarding flush (3) VS Code is not a compiler but I assume you're using the Microsoft compiler? I am unable to make it work at all with the Microsoft compiler but it will work fine in Clang/GCC.
      – yuri
      Aug 17 at 20:02










    • No worries I will look into this, thanks! I'm using gcc (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609 Copyright (C) 2015 Free Software Foundation, Inc. through the Linux subsystem for Windows 10
      – greg
      Aug 17 at 20:28










    • Oh right, you even said so. My bad. I can make it work with GCC 5.4 however I am not using the Linux subsystem for W10 so I can't replicate your exact environment but afaik there is nothing needing those headers in your source code. What kind of errors are you getting? Did you try an online compiler to compare the output?
      – yuri
      Aug 17 at 20:34










    • They're mostly "was not declared in this scope" errors. Trying out Wandbox to showcase this here wandbox.org/permlink/kCpmFHwhLNeeYXVj
      – greg
      Aug 17 at 20:49















    great suggestions, after a quick search valgrind seems very useful, thanks. My questions are: in place of endl would you suggest I use n? In what scenario should I flush the buffer? I'm using VS Code as my editor and the C++ 11 compile command from my original post, when I replace my usings with just #include <cstddef> #include <cstdlib> I get compile errors, is this expected or am I missing something?
    – greg
    Aug 17 at 19:45




    great suggestions, after a quick search valgrind seems very useful, thanks. My questions are: in place of endl would you suggest I use n? In what scenario should I flush the buffer? I'm using VS Code as my editor and the C++ 11 compile command from my original post, when I replace my usings with just #include <cstddef> #include <cstdlib> I get compile errors, is this expected or am I missing something?
    – greg
    Aug 17 at 19:45




    1




    1




    (1) Sorry I forgot to mention n as the alternative, I'll edit it in. (2) Have a look at this regarding flush (3) VS Code is not a compiler but I assume you're using the Microsoft compiler? I am unable to make it work at all with the Microsoft compiler but it will work fine in Clang/GCC.
    – yuri
    Aug 17 at 20:02




    (1) Sorry I forgot to mention n as the alternative, I'll edit it in. (2) Have a look at this regarding flush (3) VS Code is not a compiler but I assume you're using the Microsoft compiler? I am unable to make it work at all with the Microsoft compiler but it will work fine in Clang/GCC.
    – yuri
    Aug 17 at 20:02












    No worries I will look into this, thanks! I'm using gcc (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609 Copyright (C) 2015 Free Software Foundation, Inc. through the Linux subsystem for Windows 10
    – greg
    Aug 17 at 20:28




    No worries I will look into this, thanks! I'm using gcc (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609 Copyright (C) 2015 Free Software Foundation, Inc. through the Linux subsystem for Windows 10
    – greg
    Aug 17 at 20:28












    Oh right, you even said so. My bad. I can make it work with GCC 5.4 however I am not using the Linux subsystem for W10 so I can't replicate your exact environment but afaik there is nothing needing those headers in your source code. What kind of errors are you getting? Did you try an online compiler to compare the output?
    – yuri
    Aug 17 at 20:34




    Oh right, you even said so. My bad. I can make it work with GCC 5.4 however I am not using the Linux subsystem for W10 so I can't replicate your exact environment but afaik there is nothing needing those headers in your source code. What kind of errors are you getting? Did you try an online compiler to compare the output?
    – yuri
    Aug 17 at 20:34












    They're mostly "was not declared in this scope" errors. Trying out Wandbox to showcase this here wandbox.org/permlink/kCpmFHwhLNeeYXVj
    – greg
    Aug 17 at 20:49




    They're mostly "was not declared in this scope" errors. Trying out Wandbox to showcase this here wandbox.org/permlink/kCpmFHwhLNeeYXVj
    – greg
    Aug 17 at 20:49










    up vote
    5
    down vote













    Use std::vector<int> to store the numbers



    Your post does contain




    you are given two non-empty linked lists representing two non-negative integers.




    It's not clear whether that is conceptual or more. If it is conceptual, I would strongly recommend using std::vector<int> to store the numbers.



    If you do that, the code to construct the numbers gets really simple. As an example from proveDoubleCarry, the code to construct the two numbers can be 



    std::vector<int> l19;
    std::vector<int> l21, 9, 9, 9, 8, 9, 9;


    instead of



    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;


    Get rid of the class Solution.



    I don't see any need for the class. It does not provide any more abstractions that a simple function cannot provide. It can be replaced by a function



    std::vector<int> addTwoNumbers(std::vector<int> const& l1,
     std::vector<int> const& l2);


    Use recursive function to add the numbers



    Implementation of addTwoNumbers becomes simple to understand by using a recursive helper function.



    Here's how the two look in my implementation.



    void addTwoNumbers(std::vector<int>::const_iterator iter1,
     std::vector<int>::const_iterator end1,
     std::vector<int>::const_iterator iter2,
     std::vector<int>::const_iterator end2,
     int carry,
     std::vector<int>& result)

     // Check for terminating condition.
     if ( iter1 == end1 && iter2 == end2 && carry == 0 )
     
     return;
     

     int sum = carry;
     if ( iter1 != end1 )
     
     sum += *iter1;
     
     if ( iter2 != end2 )
     
     sum += *iter2;
     

     carry = sum/10;
     sum = sum%10;

     result.push_back(sum);

     if ( iter1 != end1 )
     
     ++iter1;
     

     if ( iter2 != end2 )
     
     ++iter2;
     

     // Recurse
     addTwoNumbers(iter1, end1, iter2, end2, carry, result);


    std::vector<int> addTwoNumbers(std::vector<int> const& l1,
     std::vector<int> const& l2)

     std::vector<int> result;
     addTwoNumbers(l1.begin(), l1.end(),
     l2.begin(), l2.end(),
     0,
     result);

     return result;



    Print the input and output together



    It is more useful to be able to see the input and the output together. Any errors in the code would be seen more easily when both of them are printed together. Example code would be



    printNumber("First number", l1);
    printNumber("Second number", l2);
    printNumber("Result", result);


    Here's a complete listing of my updated version of your program.



    #include <iostream>
    #include <vector>
    #include <string>

    void printNumber(std::vector<int>::const_reverse_iterator iter,
     std::vector<int>::const_reverse_iterator end)

     if ( iter == end )
     
     return;
     
     std::cout << *iter;
     printNumber(++iter, end);


    void printNumber(std::string const& label,
     std::vector<int> const& num)

     std::cout << label << ": ( ";
     printNumber(num.rbegin(), num.rend());
     std::cout << " )n";


    void addTwoNumbers(std::vector<int>::const_iterator iter1,
     std::vector<int>::const_iterator end1,
     std::vector<int>::const_iterator iter2,
     std::vector<int>::const_iterator end2,
     int carry,
     std::vector<int>& result)

     // Check for terminating condition.
     if ( iter1 == end1 && iter2 == end2 && carry == 0 )
     
     return;
     

     int sum = carry;
     if ( iter1 != end1 )
     
     sum += *iter1;
     
     if ( iter2 != end2 )
     
     sum += *iter2;
     

     carry = sum/10;
     sum = sum%10;

     result.push_back(sum);

     if ( iter1 != end1 )
     
     ++iter1;
     

     if ( iter2 != end2 )
     
     ++iter2;
     

     // Recurse
     addTwoNumbers(iter1, end1, iter2, end2, carry, result);


    std::vector<int> addTwoNumbers(std::vector<int> const& l1,
     std::vector<int> const& l2)

     std::vector<int> result;
     addTwoNumbers(l1.begin(), l1.end(),
     l2.begin(), l2.end(),
     0,
     result);

     return result;



    /**
     *
     * 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()

     std::cout << "nnBasic casen";

     std::vector<int> l12, 4, 3;
     std::vector<int> l25, 6, 4;

     auto result = addTwoNumbers(l1, l2);

     printNumber("First number", l1);
     printNumber("Second number", l2);
     printNumber("Result", result);


    /**
     *
     * 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()

     std::cout << "nnUneven List sizesn";

     std::vector<int> l12, 4, 3;
     std::vector<int> l25, 6;

     auto result = addTwoNumbers(l1, l2);

     printNumber("First number", l1);
     printNumber("Second number", l2);
     printNumber("Result", result);


    /**
     *
     * 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()

     std::cout << "nnDouble Carryn";

     std::vector<int> l19;
     std::vector<int> l21, 9, 9, 9, 8, 9, 9;

     auto result = addTwoNumbers(l1, l2);

     printNumber("First number", l1);
     printNumber("Second number", l2);
     printNumber("Result", result);


    int main()

     std::cout << "Mr Robot is running prgm..." << std::endl;

     proveBasicCase();
     proveListSizeNotEqual();
     proveDoubleCarry();

     return 0;



    and its output



    Mr Robot is running prgm...


    Basic case
    First number: ( 342 )
    Second number: ( 465 )
    Result: ( 807 )


    Uneven List sizes
    First number: ( 342 )
    Second number: ( 65 )
    Result: ( 407 )


    Double Carry
    First number: ( 9 )
    Second number: ( 9989991 )
    Result: ( 9990000 )





    share|improve this answer


























      up vote
      5
      down vote













      Use std::vector<int> to store the numbers



      Your post does contain




      you are given two non-empty linked lists representing two non-negative integers.




      It's not clear whether that is conceptual or more. If it is conceptual, I would strongly recommend using std::vector<int> to store the numbers.



      If you do that, the code to construct the numbers gets really simple. As an example from proveDoubleCarry, the code to construct the two numbers can be 



      std::vector<int> l19;
      std::vector<int> l21, 9, 9, 9, 8, 9, 9;


      instead of



      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;


      Get rid of the class Solution.



      I don't see any need for the class. It does not provide any more abstractions that a simple function cannot provide. It can be replaced by a function



      std::vector<int> addTwoNumbers(std::vector<int> const& l1,
       std::vector<int> const& l2);


      Use recursive function to add the numbers



      Implementation of addTwoNumbers becomes simple to understand by using a recursive helper function.



      Here's how the two look in my implementation.



      void addTwoNumbers(std::vector<int>::const_iterator iter1,
       std::vector<int>::const_iterator end1,
       std::vector<int>::const_iterator iter2,
       std::vector<int>::const_iterator end2,
       int carry,
       std::vector<int>& result)

       // Check for terminating condition.
       if ( iter1 == end1 && iter2 == end2 && carry == 0 )
       
       return;
       

       int sum = carry;
       if ( iter1 != end1 )
       
       sum += *iter1;
       
       if ( iter2 != end2 )
       
       sum += *iter2;
       

       carry = sum/10;
       sum = sum%10;

       result.push_back(sum);

       if ( iter1 != end1 )
       
       ++iter1;
       

       if ( iter2 != end2 )
       
       ++iter2;
       

       // Recurse
       addTwoNumbers(iter1, end1, iter2, end2, carry, result);


      std::vector<int> addTwoNumbers(std::vector<int> const& l1,
       std::vector<int> const& l2)

       std::vector<int> result;
       addTwoNumbers(l1.begin(), l1.end(),
       l2.begin(), l2.end(),
       0,
       result);

       return result;



      Print the input and output together



      It is more useful to be able to see the input and the output together. Any errors in the code would be seen more easily when both of them are printed together. Example code would be



      printNumber("First number", l1);
      printNumber("Second number", l2);
      printNumber("Result", result);


      Here's a complete listing of my updated version of your program.



      #include <iostream>
      #include <vector>
      #include <string>

      void printNumber(std::vector<int>::const_reverse_iterator iter,
       std::vector<int>::const_reverse_iterator end)

       if ( iter == end )
       
       return;
       
       std::cout << *iter;
       printNumber(++iter, end);


      void printNumber(std::string const& label,
       std::vector<int> const& num)

       std::cout << label << ": ( ";
       printNumber(num.rbegin(), num.rend());
       std::cout << " )n";


      void addTwoNumbers(std::vector<int>::const_iterator iter1,
       std::vector<int>::const_iterator end1,
       std::vector<int>::const_iterator iter2,
       std::vector<int>::const_iterator end2,
       int carry,
       std::vector<int>& result)

       // Check for terminating condition.
       if ( iter1 == end1 && iter2 == end2 && carry == 0 )
       
       return;
       

       int sum = carry;
       if ( iter1 != end1 )
       
       sum += *iter1;
       
       if ( iter2 != end2 )
       
       sum += *iter2;
       

       carry = sum/10;
       sum = sum%10;

       result.push_back(sum);

       if ( iter1 != end1 )
       
       ++iter1;
       

       if ( iter2 != end2 )
       
       ++iter2;
       

       // Recurse
       addTwoNumbers(iter1, end1, iter2, end2, carry, result);


      std::vector<int> addTwoNumbers(std::vector<int> const& l1,
       std::vector<int> const& l2)

       std::vector<int> result;
       addTwoNumbers(l1.begin(), l1.end(),
       l2.begin(), l2.end(),
       0,
       result);

       return result;



      /**
       *
       * 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()

       std::cout << "nnBasic casen";

       std::vector<int> l12, 4, 3;
       std::vector<int> l25, 6, 4;

       auto result = addTwoNumbers(l1, l2);

       printNumber("First number", l1);
       printNumber("Second number", l2);
       printNumber("Result", result);


      /**
       *
       * 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()

       std::cout << "nnUneven List sizesn";

       std::vector<int> l12, 4, 3;
       std::vector<int> l25, 6;

       auto result = addTwoNumbers(l1, l2);

       printNumber("First number", l1);
       printNumber("Second number", l2);
       printNumber("Result", result);


      /**
       *
       * 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()

       std::cout << "nnDouble Carryn";

       std::vector<int> l19;
       std::vector<int> l21, 9, 9, 9, 8, 9, 9;

       auto result = addTwoNumbers(l1, l2);

       printNumber("First number", l1);
       printNumber("Second number", l2);
       printNumber("Result", result);


      int main()

       std::cout << "Mr Robot is running prgm..." << std::endl;

       proveBasicCase();
       proveListSizeNotEqual();
       proveDoubleCarry();

       return 0;



      and its output



      Mr Robot is running prgm...


      Basic case
      First number: ( 342 )
      Second number: ( 465 )
      Result: ( 807 )


      Uneven List sizes
      First number: ( 342 )
      Second number: ( 65 )
      Result: ( 407 )


      Double Carry
      First number: ( 9 )
      Second number: ( 9989991 )
      Result: ( 9990000 )





      share|improve this answer
























        up vote
        5
        down vote










        up vote
        5
        down vote









        Use std::vector<int> to store the numbers



        Your post does contain




        you are given two non-empty linked lists representing two non-negative integers.




        It's not clear whether that is conceptual or more. If it is conceptual, I would strongly recommend using std::vector<int> to store the numbers.



        If you do that, the code to construct the numbers gets really simple. As an example from proveDoubleCarry, the code to construct the two numbers can be 



        std::vector<int> l19;
        std::vector<int> l21, 9, 9, 9, 8, 9, 9;


        instead of



        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;


        Get rid of the class Solution.



        I don't see any need for the class. It does not provide any more abstractions that a simple function cannot provide. It can be replaced by a function



        std::vector<int> addTwoNumbers(std::vector<int> const& l1,
         std::vector<int> const& l2);


        Use recursive function to add the numbers



        Implementation of addTwoNumbers becomes simple to understand by using a recursive helper function.



        Here's how the two look in my implementation.



        void addTwoNumbers(std::vector<int>::const_iterator iter1,
         std::vector<int>::const_iterator end1,
         std::vector<int>::const_iterator iter2,
         std::vector<int>::const_iterator end2,
         int carry,
         std::vector<int>& result)

         // Check for terminating condition.
         if ( iter1 == end1 && iter2 == end2 && carry == 0 )
         
         return;
         

         int sum = carry;
         if ( iter1 != end1 )
         
         sum += *iter1;
         
         if ( iter2 != end2 )
         
         sum += *iter2;
         

         carry = sum/10;
         sum = sum%10;

         result.push_back(sum);

         if ( iter1 != end1 )
         
         ++iter1;
         

         if ( iter2 != end2 )
         
         ++iter2;
         

         // Recurse
         addTwoNumbers(iter1, end1, iter2, end2, carry, result);


        std::vector<int> addTwoNumbers(std::vector<int> const& l1,
         std::vector<int> const& l2)

         std::vector<int> result;
         addTwoNumbers(l1.begin(), l1.end(),
         l2.begin(), l2.end(),
         0,
         result);

         return result;



        Print the input and output together



        It is more useful to be able to see the input and the output together. Any errors in the code would be seen more easily when both of them are printed together. Example code would be



        printNumber("First number", l1);
        printNumber("Second number", l2);
        printNumber("Result", result);


        Here's a complete listing of my updated version of your program.



        #include <iostream>
        #include <vector>
        #include <string>

        void printNumber(std::vector<int>::const_reverse_iterator iter,
         std::vector<int>::const_reverse_iterator end)

         if ( iter == end )
         
         return;
         
         std::cout << *iter;
         printNumber(++iter, end);


        void printNumber(std::string const& label,
         std::vector<int> const& num)

         std::cout << label << ": ( ";
         printNumber(num.rbegin(), num.rend());
         std::cout << " )n";


        void addTwoNumbers(std::vector<int>::const_iterator iter1,
         std::vector<int>::const_iterator end1,
         std::vector<int>::const_iterator iter2,
         std::vector<int>::const_iterator end2,
         int carry,
         std::vector<int>& result)

         // Check for terminating condition.
         if ( iter1 == end1 && iter2 == end2 && carry == 0 )
         
         return;
         

         int sum = carry;
         if ( iter1 != end1 )
         
         sum += *iter1;
         
         if ( iter2 != end2 )
         
         sum += *iter2;
         

         carry = sum/10;
         sum = sum%10;

         result.push_back(sum);

         if ( iter1 != end1 )
         
         ++iter1;
         

         if ( iter2 != end2 )
         
         ++iter2;
         

         // Recurse
         addTwoNumbers(iter1, end1, iter2, end2, carry, result);


        std::vector<int> addTwoNumbers(std::vector<int> const& l1,
         std::vector<int> const& l2)

         std::vector<int> result;
         addTwoNumbers(l1.begin(), l1.end(),
         l2.begin(), l2.end(),
         0,
         result);

         return result;



        /**
         *
         * 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()

         std::cout << "nnBasic casen";

         std::vector<int> l12, 4, 3;
         std::vector<int> l25, 6, 4;

         auto result = addTwoNumbers(l1, l2);

         printNumber("First number", l1);
         printNumber("Second number", l2);
         printNumber("Result", result);


        /**
         *
         * 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()

         std::cout << "nnUneven List sizesn";

         std::vector<int> l12, 4, 3;
         std::vector<int> l25, 6;

         auto result = addTwoNumbers(l1, l2);

         printNumber("First number", l1);
         printNumber("Second number", l2);
         printNumber("Result", result);


        /**
         *
         * 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()

         std::cout << "nnDouble Carryn";

         std::vector<int> l19;
         std::vector<int> l21, 9, 9, 9, 8, 9, 9;

         auto result = addTwoNumbers(l1, l2);

         printNumber("First number", l1);
         printNumber("Second number", l2);
         printNumber("Result", result);


        int main()

         std::cout << "Mr Robot is running prgm..." << std::endl;

         proveBasicCase();
         proveListSizeNotEqual();
         proveDoubleCarry();

         return 0;



        and its output



        Mr Robot is running prgm...


        Basic case
        First number: ( 342 )
        Second number: ( 465 )
        Result: ( 807 )


        Uneven List sizes
        First number: ( 342 )
        Second number: ( 65 )
        Result: ( 407 )


        Double Carry
        First number: ( 9 )
        Second number: ( 9989991 )
        Result: ( 9990000 )





        share|improve this answer














        Use std::vector<int> to store the numbers



        Your post does contain




        you are given two non-empty linked lists representing two non-negative integers.




        It's not clear whether that is conceptual or more. If it is conceptual, I would strongly recommend using std::vector<int> to store the numbers.



        If you do that, the code to construct the numbers gets really simple. As an example from proveDoubleCarry, the code to construct the two numbers can be 



        std::vector<int> l19;
        std::vector<int> l21, 9, 9, 9, 8, 9, 9;


        instead of



        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;


        Get rid of the class Solution.



        I don't see any need for the class. It does not provide any more abstractions that a simple function cannot provide. It can be replaced by a function



        std::vector<int> addTwoNumbers(std::vector<int> const& l1,
         std::vector<int> const& l2);


        Use recursive function to add the numbers



        Implementation of addTwoNumbers becomes simple to understand by using a recursive helper function.



        Here's how the two look in my implementation.



        void addTwoNumbers(std::vector<int>::const_iterator iter1,
         std::vector<int>::const_iterator end1,
         std::vector<int>::const_iterator iter2,
         std::vector<int>::const_iterator end2,
         int carry,
         std::vector<int>& result)

         // Check for terminating condition.
         if ( iter1 == end1 && iter2 == end2 && carry == 0 )
         
         return;
         

         int sum = carry;
         if ( iter1 != end1 )
         
         sum += *iter1;
         
         if ( iter2 != end2 )
         
         sum += *iter2;
         

         carry = sum/10;
         sum = sum%10;

         result.push_back(sum);

         if ( iter1 != end1 )
         
         ++iter1;
         

         if ( iter2 != end2 )
         
         ++iter2;
         

         // Recurse
         addTwoNumbers(iter1, end1, iter2, end2, carry, result);


        std::vector<int> addTwoNumbers(std::vector<int> const& l1,
         std::vector<int> const& l2)

         std::vector<int> result;
         addTwoNumbers(l1.begin(), l1.end(),
         l2.begin(), l2.end(),
         0,
         result);

         return result;



        Print the input and output together



        It is more useful to be able to see the input and the output together. Any errors in the code would be seen more easily when both of them are printed together. Example code would be



        printNumber("First number", l1);
        printNumber("Second number", l2);
        printNumber("Result", result);


        Here's a complete listing of my updated version of your program.



        #include <iostream>
        #include <vector>
        #include <string>

        void printNumber(std::vector<int>::const_reverse_iterator iter,
         std::vector<int>::const_reverse_iterator end)

         if ( iter == end )
         
         return;
         
         std::cout << *iter;
         printNumber(++iter, end);


        void printNumber(std::string const& label,
         std::vector<int> const& num)

         std::cout << label << ": ( ";
         printNumber(num.rbegin(), num.rend());
         std::cout << " )n";


        void addTwoNumbers(std::vector<int>::const_iterator iter1,
         std::vector<int>::const_iterator end1,
         std::vector<int>::const_iterator iter2,
         std::vector<int>::const_iterator end2,
         int carry,
         std::vector<int>& result)

         // Check for terminating condition.
         if ( iter1 == end1 && iter2 == end2 && carry == 0 )
         
         return;
         

         int sum = carry;
         if ( iter1 != end1 )
         
         sum += *iter1;
         
         if ( iter2 != end2 )
         
         sum += *iter2;
         

         carry = sum/10;
         sum = sum%10;

         result.push_back(sum);

         if ( iter1 != end1 )
         
         ++iter1;
         

         if ( iter2 != end2 )
         
         ++iter2;
         

         // Recurse
         addTwoNumbers(iter1, end1, iter2, end2, carry, result);


        std::vector<int> addTwoNumbers(std::vector<int> const& l1,
         std::vector<int> const& l2)

         std::vector<int> result;
         addTwoNumbers(l1.begin(), l1.end(),
         l2.begin(), l2.end(),
         0,
         result);

         return result;



        /**
         *
         * 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()

         std::cout << "nnBasic casen";

         std::vector<int> l12, 4, 3;
         std::vector<int> l25, 6, 4;

         auto result = addTwoNumbers(l1, l2);

         printNumber("First number", l1);
         printNumber("Second number", l2);
         printNumber("Result", result);


        /**
         *
         * 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()

         std::cout << "nnUneven List sizesn";

         std::vector<int> l12, 4, 3;
         std::vector<int> l25, 6;

         auto result = addTwoNumbers(l1, l2);

         printNumber("First number", l1);
         printNumber("Second number", l2);
         printNumber("Result", result);


        /**
         *
         * 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()

         std::cout << "nnDouble Carryn";

         std::vector<int> l19;
         std::vector<int> l21, 9, 9, 9, 8, 9, 9;

         auto result = addTwoNumbers(l1, l2);

         printNumber("First number", l1);
         printNumber("Second number", l2);
         printNumber("Result", result);


        int main()

         std::cout << "Mr Robot is running prgm..." << std::endl;

         proveBasicCase();
         proveListSizeNotEqual();
         proveDoubleCarry();

         return 0;



        and its output



        Mr Robot is running prgm...


        Basic case
        First number: ( 342 )
        Second number: ( 465 )
        Result: ( 807 )


        Uneven List sizes
        First number: ( 342 )
        Second number: ( 65 )
        Result: ( 407 )


        Double Carry
        First number: ( 9 )
        Second number: ( 9989991 )
        Result: ( 9990000 )






        share|improve this answer














        share|improve this answer



        share|improve this answer








        edited Aug 20 at 13:41

























        answered Aug 18 at 6:32









        R Sahu

        3,224617




        3,224617




















            up vote
            4
            down vote













            Your Solution::addTwoNumbers routine leaks 3 list nodes per call. In the initializing part:



             ListNode *node = new ListNode(0); // <-- the only used
             ListNode *currentNode = new ListNode(0);
             currentNode = node;

             ListNode *currentL1 = new ListNode(0);
             ListNode *currentL2 = new ListNode(0);
             currentL1 = l1;
             currentL2 = l2;


            all allocated nodes except the first one are abandoned: you allocate them, but you never use or delete them.
            Do appropriate initializataion instead:



             ListNode *node = new ListNode(0);
             ListNode *currentNode = node;

             ListNode *currentL1 = l1;
             ListNode *currentL2 = l2;





            share|improve this answer






















            • Great point, I anticipated some memory error and appreciate the code example given to resolve it. will implement once I refactor. Thanks!
              – greg
              Aug 20 at 16:22














            up vote
            4
            down vote













            Your Solution::addTwoNumbers routine leaks 3 list nodes per call. In the initializing part:



             ListNode *node = new ListNode(0); // <-- the only used
             ListNode *currentNode = new ListNode(0);
             currentNode = node;

             ListNode *currentL1 = new ListNode(0);
             ListNode *currentL2 = new ListNode(0);
             currentL1 = l1;
             currentL2 = l2;


            all allocated nodes except the first one are abandoned: you allocate them, but you never use or delete them.
            Do appropriate initializataion instead:



             ListNode *node = new ListNode(0);
             ListNode *currentNode = node;

             ListNode *currentL1 = l1;
             ListNode *currentL2 = l2;





            share|improve this answer






















            • Great point, I anticipated some memory error and appreciate the code example given to resolve it. will implement once I refactor. Thanks!
              – greg
              Aug 20 at 16:22












            up vote
            4
            down vote










            up vote
            4
            down vote









            Your Solution::addTwoNumbers routine leaks 3 list nodes per call. In the initializing part:



             ListNode *node = new ListNode(0); // <-- the only used
             ListNode *currentNode = new ListNode(0);
             currentNode = node;

             ListNode *currentL1 = new ListNode(0);
             ListNode *currentL2 = new ListNode(0);
             currentL1 = l1;
             currentL2 = l2;


            all allocated nodes except the first one are abandoned: you allocate them, but you never use or delete them.
            Do appropriate initializataion instead:



             ListNode *node = new ListNode(0);
             ListNode *currentNode = node;

             ListNode *currentL1 = l1;
             ListNode *currentL2 = l2;





            share|improve this answer














            Your Solution::addTwoNumbers routine leaks 3 list nodes per call. In the initializing part:



             ListNode *node = new ListNode(0); // <-- the only used
             ListNode *currentNode = new ListNode(0);
             currentNode = node;

             ListNode *currentL1 = new ListNode(0);
             ListNode *currentL2 = new ListNode(0);
             currentL1 = l1;
             currentL2 = l2;


            all allocated nodes except the first one are abandoned: you allocate them, but you never use or delete them.
            Do appropriate initializataion instead:



             ListNode *node = new ListNode(0);
             ListNode *currentNode = node;

             ListNode *currentL1 = l1;
             ListNode *currentL2 = l2;






            share|improve this answer














            share|improve this answer



            share|improve this answer








            edited Aug 20 at 13:30

























            answered Aug 20 at 8:47









            CiaPan

            1,2901412




            1,2901412











            • Great point, I anticipated some memory error and appreciate the code example given to resolve it. will implement once I refactor. Thanks!
              – greg
              Aug 20 at 16:22
















            • Great point, I anticipated some memory error and appreciate the code example given to resolve it. will implement once I refactor. Thanks!
              – greg
              Aug 20 at 16:22















            Great point, I anticipated some memory error and appreciate the code example given to resolve it. will implement once I refactor. Thanks!
            – greg
            Aug 20 at 16:22




            Great point, I anticipated some memory error and appreciate the code example given to resolve it. will implement once I refactor. Thanks!
            – greg
            Aug 20 at 16:22

















             

            draft saved


            draft discarded















































             


            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f201902%2fadd-two-numbers-given-in-reverse-order-from-a-linked-list%23new-answer', 'question_page');

            );

            Post as a guest
































































            Comments

            Post a Comment

            Popular posts from this blog

            What does second last employer means? [closed]

            Image
            Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote -3 down vote favorite Say, for example I have worked in the following companies, Company A => 2010 - 2011 Company B => 2011 - 2012 Company C => 2012 - Till Date Company D => Have offer Now assume Company D is asking to submit documents from my second last employer. So from the list of companies given, which company would be qualified as second last employer? software-industry employer share | improve this question asked Aug 10 '14 at 5:16 Rajaprabhu Aravindasamy 559 1 6 13 closed as off-topic by Jim G., jmort253 ♦ Aug 11 '14 at 1:58 This question appears to be off-topic. The users who voted to close gave this specific reason: "Questions seeking advice on company-specific regulations, agreements, or policies should be directed to your manager or HR department. Questions that address...
            Read more

            List of Gilmore Girls characters

            Image
            The season three cast—(Back row): Lane, Michel, Paris, Emily, Richard, Sookie, Miss Patty, Kirk; Front row: Jess, Luke, Lorelai, Rory, Dean This is a list of characters for the comedy-drama television series Gilmore Girls . Contents 1 Main characters 1.1 Lorelai Gilmore 1.2 Rory Gilmore 1.3 Sookie St. James 1.4 Lane Kim 1.5 Michel Gerard 1.6 Luke Danes 1.7 Emily Gilmore 1.8 Richard Gilmore 1.9 Paris Geller 1.10 Dean Forester 1.11 Jess Mariano 1.12 Kirk Gleason 1.13 Jason Stiles 1.14 Logan Huntzberger 2 Major recurring characters 2.1 Christopher Hayden 2.2 Jackson Belleville 2.3 Mrs. Kim 2.4 Tristin DuGray 2.5 Max Medina 2.6 Taylor Doose 2.7 Dave Rygalski 2.8 Marty 3 Recurring characters 3.1 Stars Hollow 3.2 Chilton 3.3 Yale 3.4 Other 4 Notable guest stars 5 Unseen characters 6 Notes 7 References Main characters Actor Character Appearances Season 1 Season 2 Season 3 Season 4 Season 5 Season 6 Season 7 A Year in the Life Lauren Graham Lorelai Gilmore...
            Read more

            One-line joke

            A one-liner is a joke that is delivered in a single line. A good one-liner is said to be pithy - concise and meaningful. [1] Comedians and actors use this comedic method as part of their act, e.g. Jimmy Carr, Tommy Cooper, Rodney Dangerfield, Norm Macdonald, Ken Dodd, Stewart Francis, Zach Galifianakis, Mitch Hedberg, Anthony Jeselnik, Milton Jones, Shappi Khorsandi, Jay London, Mark Linn-Baker, Demetri Martin, Groucho Marx, Dan Mintz, Emo Philips, Tim Vine, Steven Wright and Henny Youngman and Arnold Schwarzenegger. [ citation needed ] Many fictional characters are also known to deliver one-liners, including James Bond, who usually includes pithy and laconic quips after disposing of a villain. [ citation needed ] Examples "A baby seal walks into a club." "A dyslexic man walks into a bra." (Anonymous) "There are three types of people, those who can count and those who can't." "Venison's dear, isn't it?" (Jimmy Carr) "An escala...
            Read more