本文共 3495 字，大约阅读时间需要 11 分钟。

1 问题

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头

2 解决

思想：和数学的加法相同，首先让l1第一个元素2和l2的第一个元素5相加，结果保存在result的第一个元素位置。需要注意的是，如果结果大于10，会产生进位。

情况1：如上图，l1和l2长度相同，且最高位不在产生进位，即3+4+1=8<10,那么结果会和l1,l2有相同的长度。

情况2：l1的长度<l2的长度。那么当l1遍历结束后，l2的元素需要和进位相加至结束。如 l1:9和l2:1->1->1,结果是  0->2->1

情况3：与情况2相反。

需要注意的是，如果最高位产生进位，那么最后链表result需要多开辟一个位置存放进位，即最高位。如 l1:9->9和l2:1->1,结果是  0->1->1.

/** * 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) {                ListNode * head = NULL;//结果        ListNode * pNew = head;                ListNode* p = l1;        ListNode* q = l2;        int     cnt = 0;                while (  (p != NULL) && (q != NULL)  )//依次取出l1,l2中元素直至其中一个链表结束        {            int sum = cnt + p->val + q->val;//计算两个元素和进位相加的结果            if ( sum >= 10 )//结果大于10            {                int tmp = sum;                sum = sum % 10;//余数                cnt = tmp / 10;//进位                                }            else//如果没有产生进位，及时将以前产生进位清零            {                cnt = 0;            }                        ListNode * tmp = new ListNode(sum);//创建新结点存放            if ( pNew == NULL )//如果是结果的首元素            {                head = pNew = tmp;            }            else//否则插入到结果的最后位置            {                pNew->next = tmp;                pNew = pNew->next;            }                        p = p->next;//迭代到下一个位置            q = q->next;                                }                if ( NULL == p )//如果l1 结束了        {            while(  q != NULL  )//判断l2是否遍历结束            {                int sum = cnt +  q->val;                if ( sum >= 10 )                {                    int tmp = sum;                    sum = sum % 10;                    cnt = tmp / 10;                }                else                {                    cnt = 0;                }                ListNode * tmp = new ListNode(sum);                if ( pNew == NULL )                {                    head = pNew = tmp;                }                else                {                    pNew->next = tmp;                    pNew = pNew->next;                }                q = q->next;            }        }                else if ( NULL == q )//        {            while(  p != NULL  )            {                int sum = cnt +  p->val;                if ( sum >= 10 )                {                    int tmp = sum;                    sum = sum % 10;                    cnt = tmp / 10;                }                else                {                    cnt = 0;                }                ListNode * tmp = new ListNode(sum);                if ( pNew == NULL )                {                    head = pNew = tmp;                }                else                {                    pNew->next = tmp;                    pNew = pNew->next;                }                p = p->next;            }        }                        if ( cnt != 0 )//如果最高位相加产生进位        {                ListNode * tmp = new ListNode(cnt);                if ( pNew == NULL )                {                    head = pNew = tmp;                }                else                {                    pNew->next = tmp;                    pNew = pNew->next;                }        }        return head;            }};