[LeetCode 2] Add Two Numbers [C] [Runtime : 32 MS]

1. 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.

2. Example

You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

3. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C (S=O(N))" active="active"]

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) 
{
	struct ListNode* mHead = (struct ListNode *)malloc(sizeof(struct ListNode));
	struct ListNode* mPreNode = mHead;
	int mCarry = 0, mSum = 0;

	while (l1 != NULL || l2 != NULL || mCarry != 0) 
	{
		struct ListNode* mResult = (struct ListNode *)malloc(sizeof(struct ListNode));
		mSum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + mCarry;
		mResult->val = (mSum) % 10;
		mCarry = mSum / 10;
		mPreNode = mPreNode->next = mResult;
		l1 = l1 ? l1->next : NULL;
		l2 = l2 ? l2->next : NULL;
	}
	mPreNode->next = NULL;
	return mHead->next;
}

[/restab]
[restab title="C (S=O(1))"]

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) 
{
	struct ListNode* mPreNode = l1;
	struct ListNode* mHead = l1;
	int mCarry = 0, mSum = 0;

	while (l1 != NULL && (l2 != NULL || mCarry != 0)) 
	{
		mSum = l1->val + (l2 ? l2->val : 0) + mCarry;
		l1->val = mSum % 10;
		mCarry = mSum / 10;

		mPreNode = l1;
		l1 = l1 ? l1->next : NULL;
		l2 = l2 ? l2->next : NULL;
	}

	if (l1 == NULL && l2 != NULL) {
		mPreNode->next = l2;
		l1 = l2;
	}

	while (mCarry != 0) {
		if (l1 == NULL) {
			l1 = (struct ListNode*)malloc(sizeof(struct ListNode));
			l1->next = NULL;
			l1->val = mCarry;
			mPreNode->next = l1;
			mCarry = 0;
		}
		else{
			mSum = l1->val + mCarry;
			l1->val = mSum % 10;
			mCarry = mSum / 10;
			mPreNode = l1;
			l1 = l1->next;
		}
	}

	return mHead;
}

[/restab]
[restab title="C (TEST)"]

#include

struct ListNode 
{
	int val;
	struct ListNode *next;
};

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) 
{
	/* Replace with other tabs code */
}

struct ListNode* ArrayToLink(int aArray[], int aLength)
{
	struct ListNode* aHead = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* mPreNode = aHead;

	for (int i = 0; i < aLength; i++) 
	{
		struct ListNode* mNode = (struct ListNode*)malloc(sizeof(struct ListNode));
		mNode->val = aArray[i];
		mPreNode->next = mNode;
		mPreNode = mNode;
	}
	mPreNode->next = NULL;

	return aHead;
}

int main()
{
	int mA1[] = { 1 }, mA2[] = { 9,9 };

	struct ListNode* mL1 = ArrayToLink(mA1, 1);
	struct ListNode* mL2 = ArrayToLink(mA2, 2);

	struct ListNode* mResult = addTwoNumbers(mL1->next, mL2->next);

	if (mResult != NULL) 
	{
		printf("%d", mResult->val);
		mResult = mResult->next;
	}

	while (mResult != NULL) 
	{
		printf(" -> %d", mResult->val);
		mResult = mResult->next;
	}

	system("pause");
	return 1;
}

[/restab]
[/restabs]