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

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

class Solution {
  public:
    ListNode* reverse(ListNode* pHead) {
        ListNode* lst = nullptr;
        while (pHead) {
            ListNode* tmp = pHead -> next;
            pHead -> next = lst;
            lst = pHead;
            pHead = tmp;
        }
        return lst;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        if (head1 == nullptr)  return head2;
        if (head2 == nullptr)  return head1;
        head1 = reverse(head1);
        head2 = reverse(head2);
        int cy = 0;
        int c1, c2, tmp;
        ListNode* lst = new ListNode(1);//将头节点设为1，如果最后进位为1就返回头节点，进位为0就返回第二个节点，不要头节点
        while (head1 || head2) {
            if (head1 && head2) {
                c1 = head1 -> val;
                c2 = head2 -> val;
                tmp = c1 + c2 + cy;
            } else if (head1) {
                c1 = head1 -> val;
                tmp = c1 + cy;

            } else if (head2) {
                c2 = head2 -> val;
                tmp = c2 + cy;
            }
            cy = tmp / 10;
            tmp = tmp % 10;
            ListNode* node = new ListNode(tmp);
            node -> next = lst -> next;//头插法，生成链表刚好是倒序
            lst -> next = node;
            if (head1) head1 = head1 -> next;
            if (head2) head2 = head2 -> next;
        }
        if(cy)
         return lst;
        return lst -> next;
    }
};