# C++ O(1) space except output list O(n) time, without modifying input list

• @jade86 's idea is very good, but strictly speaking, his implementation still requires O(n) space because he first allocated a temporal list and then deleted it. Inspired by his idea. I re-implemented the code in which only the result list is allocated once. So it is O(1) space except the output list. The time complexity is O(n) and it is easy to read.

`````` * Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int n1=0, n2=0, sum=0;
ListNode *cur1=l1, *cur2= l2, *res=nullptr;
while(cur1!=nullptr) {cur1=cur1->next;n1++;}  // count the number of digits
while(cur2!=nullptr) {cur2=cur2->next;n2++;}
cur1=l1;cur2=l2;
while(n1>0 && n2>0)
{
sum=0;
if(n1>=n2){sum+=cur1->val;cur1=cur1->next;n1--;}
if(n2>n1) {sum+=cur2->val;cur2=cur2->next;n2--;}
res=addToFront(sum,res);        // calculate the sum and put the result in a reverse order.
}
int carry=0;
cur1=res;

while(cur1!=nullptr)               // propagate down the carries
{
sum=cur1->val+carry;
cur1->val=sum%10;
carry=sum/10;
cur1=cur1->next;
}
res=reverseList(res);           // reverse the result list
if(carry!=0)
res=addToFront(carry, res);   // add 1 to the front of list if needed
return res;

}
{