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

刷题小白记录一下，
主要思路：
1.将已有链表反转；
2.若两个链表均不为空，则将不为空的部分相加及进位；
3.若某个链表为空时，另外一个链表不为空，将进位和非空链表相加并链接到头结点；
4.若两个链表均为空后，判断是否有进位，若有进位则将其插入链头；

不足之处：
1.存在修改原始数据的问题，且在程序返回前未将原始数据恢复；

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

class Solution {
  private:
    ListNode* Reverse(ListNode* head) {
        ListNode* newHead = new ListNode(-1), *p;
        newHead->next = head;
        p = head;
        while (p->next) {
            ListNode* temp = p->next;
            p->next = temp->next;
            temp->next = newHead->next;
            newHead->next = temp;
        }
        p = newHead->next;
        delete newHead;
        return p;
    }
  public:
    /**
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        ListNode* p = Reverse(head1);
        ListNode* q = Reverse(head2);
        ListNode* newHead = new ListNode(-1);
        int tempResult = 0, carry = 0;
        while ( p && q ) {
            tempResult = p->val + q->val + carry;
            carry = tempResult / 10;
            tempResult %= 10;
            ListNode* temp = new ListNode(tempResult);
            temp->next = newHead->next;
            newHead->next = temp;
            p = p->next;
            q = q->next;
        }
        if (q) p = q;
        while ( p ) {
            tempResult = p->val + carry;
            carry = tempResult / 10;
            tempResult %= 10;
            ListNode* temp = new ListNode(tempResult);
            temp->next = newHead->next;
            newHead->next = temp;
            p = p->next;
        }
        if( carry ) {
            ListNode* temp = new ListNode(carry);
            temp->next = newHead->next;
            newHead->next = temp;
        }
        p = newHead->next;
        delete newHead;
        return p;
    }
};