2.add-two-numbers.md

2. Add Two Numbers

• 描述：难度medium
• 有两个链表l1，l2（没有头节点），长度可能不同。l1和l2的每个值都是数字0-9。 将l1和l2相加（看成逆序存储的十进制数），输出结果（一个逆序存储数字的链表，没有头节点）。 Example: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.

1. 思路 考虑两种情况：

• l1和l2长度不同
• l1和l2遍历完毕，但是仍然有进位的情形：如99+3=102的1，由于是逆序，1是放在最后的。 方法：从前往后遍历两个链表，l1当前位+l2当前位+上次进位，每次保存为结果链表res的元素。

2. 实现

 *//**
 * 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* res_head = new ListNode(-1);  //保存结果的链表的头节点
        ListNode* pointer = res_head;   //pointer遍历结果res
        int sum, carry=0, cur;
        //考虑到l1和l2长度不同的情况
        while(l1!=NULL || l2!=NULL)
        {
            sum=0;
            if(l1!=NULL)
            {
                sum += l1->val;
                l1 = l1->next;
            }
            if(l2!=NULL)
            {
                sum += l2->val;
                l2 = l2->next;
            }
            cur = (sum + carry)%10;     //当前值 = (l1当前位+l2当前位+上次进位)%10
            carry = (sum + carry)/10; //本次进位 = (l1当前位+l2当前位+上次进位)/10
            
            pointer->next = new ListNode(cur);  //new一个listnode来保存当前值cur
            pointer = pointer->next;            //指向结果链表的指针后移
        }
        
        //考虑l1和l2遍历完毕，但是仍然有进位的情形：如99+3=102的1，由于是逆序，1是放在最后的。
        if(carry==1)    
            pointer->next = new ListNode(carry);
        
        return res_head->next;      //res_head是指向头节点的指针，所以这里返回的是res_head->next
    }
};

3. 和2一样

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
     int flag=0;     
     ListNode* sum = new  ListNode(-1);
     ListNode* head = sum;

    while(l1!=NULL || l2!=NULL)
    {
        if(l1==NULL)
        {
            sum->next = new ListNode((flag + l2->val)%10);
            flag = (flag + l2->val)/10;  //进位
            sum = sum->next;  //移动
            l2 = l2->next;
        }
        else if(l2==NULL)
        {
            sum->next = new ListNode((flag + l1->val)%10);
            flag = (flag + l1->val)/10;  //进位
            sum = sum->next;  //移动
            l1 = l1->next;
        }
        else{
            sum->next = new ListNode((flag + l1->val + l2->val)%10);
            flag = (flag + l1->val + l2->val)/10;  //进位
            sum = sum->next;  //移动
            l1 = l1->next;
            l2 = l2->next;
        }
    }
    if(flag) //两个链表元素都遍历完毕，此时还有进位
    {
        sum->next = new ListNode(flag);
    }

    return head->next;
    }
};