题解 | #链表相加(二)#

```/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* reverse(ListNode* head)//反转链表，模拟实际加法，从低位往高位算。
    {                                
        if(head==nullptr)
            return head;
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur)
        {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        ListNode* head = nullptr;
        ListNode* tail = nullptr;
        int carry = 0;//进位标志
         head1 = reverse(head1);
         head2 = reverse(head2);
        while(head1 || head2)
        {
            int n1 = head1 ? head1->val:0;
            int n2 = head2 ? head2->val:0;
            int sum = n1 + n2 + carry;
            if(!head)
            {
                head = tail = new ListNode(sum%10);//如果head还没有，则先建立head;
            }
            else
            {
                tail->next = new ListNode(sum%10);//如果已经有head,那么便不断加到后面。
                tail = tail->next;
            }
            carry = sum / 10;//看是否有进位
            if(head1)head1 = head1->next;
            if(head2)head2 = head2->next;
        }
        if(carry>0)
            tail->next = new ListNode(1);//如果最后面还有进位，那么在后面再建立一个节点，类似于99+1=100
        ListNode* p = reverse(head);结果再反转回去。
        
        return p;
    }
};