# O(n) time, O(n) space C/C++ solution, no reversal, no recursion, no change to input lists

• I tried a different way, using arrays. It is not that fast (49 ms), but still O(n) time, O(n) space. A similar way is to calculate in link lists and record results in an array, then process this array into a new link list.

I used 'x' to represent an empty space, since an uninitialized element at the first position will cause an error when processing into a link list. It can be anything outside the digit range.

``````char* addition(const char* add1, int length1, const char* add2, int length2)
{
int i, flag = 0, diff = length1 - length2;;
char* output = (char*)malloc(length1 + 1);
for (i = length1 - 1; i >= diff; i--)
{
int tempdigi, tail1, tail2;
tempdigi = tail1 + tail2 + flag;
flag = 0;
if (tempdigi >= 10)
{
tempdigi -= 10;
flag = 1;
}
output[i + 1] = tempdigi;
}
//copy the remaining digits
if (diff > 0)
{
i = diff - 1;
while (i >= 0)
{
int tempdigi = add1[i] + flag;
flag = 0;
if (tempdigi >= 10)
{
tempdigi %= 10;
flag = 1;
}
output[i + 1] = tempdigi;
i--;
}
}
if (flag == 1)
output[0] = 1;
else output[0] = 'x';
return output;
}

{
int count = 0;
while (list != NULL)
{
count++;
list = list->next;
}
return count;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode *output = (struct ListNode*)malloc(sizeof(struct ListNode));
int count1 = 0, count2 = 0;
while (l1 != NULL)
{
arr1[count1] = l1->val;
count1++;
l1 = l1->next;
}
while (l2 != NULL)
{
arr2[count2] = l2->val;
count2++;
l2 = l2->next;
}
char* sum;
if (count1 >= count2)
sum = addition(arr1, count1, arr2, count2);
else
sum = addition(arr2, count2, arr1, count1);
int len = 1 + (count1 > count2 ? count1 : count2);
int i = 0;
while ((sum[i] == 0 || sum[i]=='x') && i < len)
i++;
if (i == len)
{
output->val = 0;
output->next = NULL;
return output;
}
output->val = sum[i];
i++;
struct ListNode *last = output;
while (i < len)
{
struct ListNode* nextNode = (struct ListNode*)malloc(sizeof(struct ListNode));
last->next = nextNode;
last = nextNode;
nextNode->val = sum[i];
i++;
}
free(sum);
free(arr1);
free(arr2);
last->next = NULL;
return output;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.