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

暴力解法：将相加结果覆盖到链表head1上

/**
 * 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* ReverseList(ListNode* pHead)
    {
        if(!pHead)
            return nullptr;
        ListNode* curr = pHead;
        ListNode* pre = nullptr;
        while(curr)
        {
            ListNode* temp = curr->next;
            curr->next = pre;
            pre = curr;
            curr = temp;
        }
        return pre;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        head1 = ReverseList(head1);
        head2 = ReverseList(head2);
        ListNode* res = new ListNode(0);
        res->next = head1;
        ListNode* pre = res;
        int ones = 0;
        int tens = 0;
        while(head1 && head2)
        {
            int sum = head1->val + head2->val + tens;
            ones = sum % 10;
            tens = sum / 10;
            head1->val = ones;
            head1 = head1->next;
            head2 = head2->next;
            pre = pre->next;
        }
        if(head2)
        {
            pre->next = head2;
            head1 = head2;
        }
        while(head1 && tens>0)
        {
            if(head1->next == nullptr)
                pre = head1;
            int sum = head1->val + tens;
            ones = sum % 10;
            tens = sum / 10;
            head1->val = ones;
            head1 = head1->next;
        }
        if(tens>0)
        {
            ListNode* end = new ListNode(tens);
            pre->next = end;    
        }
        return ReverseList(res->next);
    }
};

简洁写法

/**
 * 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* ReverseList(ListNode* pHead)
    {
        if(!pHead)
            return nullptr;
        ListNode* curr = pHead;
        ListNode* pre = nullptr;
        while(curr)
        {
            ListNode* temp = curr->next;
            curr->next = pre;
            pre = curr;
            curr = temp;
        }
        return pre;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        //简洁写法，用新的链表存储结果
        //任意一个链表为空，返回另一个
        if(head1 == nullptr)
            return head2;
        if(head2 == nullptr)
            return head1;
        //反转两个链表
        head1 = ReverseList(head1);
        head2 = ReverseList(head2);
        //添加表头
        ListNode* res = new ListNode(0);
        ListNode* head = res;
        //进位符号
        int carry = 0;
        //只要某个链表没有结束或者还有进位
        while(head1 || head2 || carry)
        {
            //链表不为空则取其值
            int val1 = (head1 == nullptr)?0:head1->val;
            int val2 = (head2 == nullptr)?0:head2->val;
            //相加
            int sum = val1 + val2 + carry;
            //获取进位
            carry = sum / 10;
            sum %= 10;
            //添加元素
            head->next = new ListNode(sum);
            head = head->next;
            //移动下一个
            if(head1)
                head1 = head1->next;
            if(head2)
                head2 = head2->next;
        }
        //结果反转回来
        return ReverseList(res->next);
    }
};