/**                 Runtime:26ms
**1for
**2head
**3
**Editorial Solution
**/
/**
 * 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 len1 = 0, len2 = 0, len = 0, carry = 0;
	ListNode *lp1 = l1, *lp2 = l2, *head = NULL, *lp = NULL;
	while (lp1->next)
	{
		len1++;
		lp1 = lp1->next;
	}
	while (lp2->next)
	{
		len2++;
		lp2 = lp2->next;
	}
	len = (len1>len2) ? len2 : len1;
	lp1 = l1;
	lp2 = l2;
	head = new ListNode(carry);
	lp = head;
	head->val = lp1->val + lp2->val;
	lp1 = lp1->next;
	lp2 = lp2->next;
	for (int i = 0; i < len; i++)
	{
		if (lp->val >= 10)
		{
			lp->val -= 10;
			carry = 1;
		}
		lp->next = new ListNode(carry);
		lp = lp->next;
		lp->val += lp1->val + lp2->val;
		carry = 0;
		lp1 = lp1->next;
		lp2 = lp2->next;
	}
	if (!lp1 && ! lp2)
	{
	    if(lp->val >= 10)
	    {
		    lp->next = new ListNode(1);
		    lp->val -= 10;
		    lp = lp->next;
	    }
	}
	else
	{
        //
		ListNode *last = (lp1 == NULL) ? lp2 : lp1;
		while (last)
		{
			if (lp->val >= 10)
			{
				lp->val -= 10;
				carry = 1;
			}
			lp->next = new ListNode(carry);
			lp = lp->next;
			lp->val += last->val;
			carry = 0;
			last = last->next;
		}
	}
    //9
	if (lp->val >= 10)
	{
		lp->val -= 10;
		lp->next = new ListNode(1);
		lp = lp->next;
	}
	lp->next = NULL;
	return head;
    }
};