leetcode第四题--Add Two Numbers

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Problem:

You are given two linked lists representing two non-negative numbers. 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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

一开始就是想到先把第一个list转换成一个数，然后把第二个转换成第二个数，然后相加后，再把相加的值变成list。代码如下

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {

        int a = , b = , ans = , flag = ;

        int index1 = , index2 = ;

        ListNode *temp1, *temp2, *result;

        temp1 = l1;

        temp2 = l2;

        while(temp1->next != NULL )

        {

            index1++;

            a += (temp1 -> next -> val) * (int)pow(,index1);

        }

        while(temp2 -> next != NULL)

        {

            index2++;

            b += temp2 ->next -> val * (int)pow(, index2);

        }

        ans = a + b;

        result -> val = ans%;

        result -> next = NULL;

        flag = ans/;

        while(flag)

        {

            ListNode *added = new ListNode(flag%10);

            result ->next = added;

            flag = flag/;

        }

        return result;

    }

然后是Time Limit Exceed了。那就不能这样做，应该直接在链表相加。加到某个链表结束为止。要用中间变量记住当前的进位。如果最后进位不为零（也就是为1）的话，那还是需要记录的。代码贴出如下：

class Solution {

public:

    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)

    {

        ListNode * ans = NULL, *last = NULL;

        int up = ;

        while (l1 != NULL && l2 != NULL)

        {

            int tmp = l1->val + l2->val + up;

            up = tmp / ;

            if (last == NULL)

            {

                ans = new ListNode(tmp % );

                last = ans;

            }

            else

                last = pushBack(last, tmp % );

            l1 = l1->next;

            l2 = l2->next;

        }

        while (l1 != NULL)

        {

            int tmp = l1->val + up;

            last = pushBack(last, tmp % );

            up = tmp / ;

            l1 = l1->next;

        }

        while (l2 != NULL)

        {

            int tmp = l2->val + up;

            last = pushBack(last, tmp % );

            up = tmp / ;

            l2 = l2->next;

        }

        if (up == )

        {

            ListNode * l = new ListNode(up);

            last->next = l;

        }

        return ans;

    }  

    ListNode * pushBack(ListNode * last, int val)

    {

        ListNode * l = new ListNode(val);

        last->next = l;

        return l;

    }

};