题目描述：

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 *head = new ListNode(0);    ListNode *p = head;    int sum = 0;    while (l1 != NULL || l2 != NULL)    {        if (l1 != NULL)        {            sum += l1->val;            l1 = l1->next;        }        if (l2 != NULL)        {            sum += l2->val;            l2 = l2->next;        }        p->next = new ListNode(sum % 10);        p = p->next;        sum /= 10;    }    if(sum)        p->next = new ListNode(1);    return head->next;}

 

原文链接：

ps:

　　代码AC只是第一步，要精益求精！