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


  • 0

    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;
    		tail1 = add1[i];
    		tail2 = add2[i - diff];
    		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 countlinklist(struct ListNode* list)
    {
    	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));
    	char* arr1 = (char*)malloc(countlinklist(l1));
    	char* arr2 = (char*)malloc(countlinklist(l2));
    	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;
    }
    

Log in to reply
 

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