首页 > 代码库 > Add Two Numbers

Add Two Numbers

题目描述:

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

  起初,这道题目被我想简单了。我用两个int值分别保存两个链表所表示的值,然后计算它们的和,最后把结果转换为链表。然而链表所能表示的值可以无限大,超出了int的存储范围。

后来自己思索了下,写出了以下代码:

solution1:

struct ListNode {    int val;    ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {    int first = 0;    int second = 0;    int carry = 0;    int sum = 0;    ListNode *list = new ListNode(-1);    ListNode *p = list;    while (l1 && l2)    {        first = l1->val;        second = l2->val;        sum = (first + second + carry) % 10;        if(first + second + carry >= 10)            carry = 1;        else            carry = 0;        p->next = new ListNode(sum);        p = p->next;        l1 = l1->next;        l2 = l2->next;    }    while (l1)    {        first = l1->val;        if (carry)        {            sum = (first + carry) % 10;            if(first + carry >= 10)                carry = 1;            else                carry = 0;        }        else        {            sum = first;        }        p->next = new ListNode(sum);        p = p->next;        l1 = l1->next;    }    while (l2)    {        second = l2->val;        if (carry)        {            sum = (second + carry) % 10;            if(second + carry >= 10)                carry = 1;            else                carry = 0;        }        else        {            sum = second;        }        p->next = new ListNode(sum);        p = p->next;        l2 = l2->next;    }    if (carry)    {        p->next = new ListNode(1);    }    return list->next;}

代码比较冗余,且可读性不高。后来在论坛上找到了别人的优化算法,真的很赞。
solution2:

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {    ListNode *p1 = l1;    ListNode *p2 = l2;    ListNode *list = new ListNode(0);    ListNode *p = list;    int sum = 0;    while (p1 != NULL || p2 != NULL)    {        if (p1 != NULL)        {            sum += p1->val;            p1 = p1->next;        }        if (p2 != NULL)        {            sum += p2->val;            p2 = p2->next;        }        p->next = new ListNode(sum % 10);        p = p->next;        sum /= 10;    }    if(sum)        p->next = new ListNode(1);    return list->next;}

原文链接:https://oj.leetcode.com/discuss/2308/is-this-algorithm-optimal-or-what
ps:

  代码AC只是第一步,要精益求精!

Add Two Numbers