题解 | #两个链表生成相加链表#

/**
 * 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类
     */
    
      //解法：模拟法
    /*
        1, 翻转链表，模拟真实场景的加法。带carry
        2, 如果遇到空的节点，val->0
    */
    //时间：O(N)， 空间O（1）
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        if (!head1) {
            return head2;
        } 
        if (!head2) {
            return head1;
        }
        ListNode* l1 = reverse(head1);
        ListNode* l2 = reverse(head2);

        int carry = 0;
        ListNode *root = new ListNode(0);
        ListNode *curr = root;
        while (l1 || l2) {
            int v1 = l1? l1->val: 0;
            int v2 = l2? l2->val: 0;
            int sum = v1 + v2 + carry;
            curr->next = new ListNode(sum % 10);
            carry = sum / 10;

            l1 = l1 ? l1->next: nullptr;
            l2 = l2 ? l2->next: nullptr;
            curr = curr->next;
        }
        
        if (carry != 0) {
            curr->next = new ListNode(carry);
            curr = curr->next;
         }
        
        return reverse(root->next);
    }
    
    ListNode* reverse(ListNode* head) {
        if (head == nullptr)  {
            return head;
        }
        ListNode* cur = head;
        ListNode* prev = nullptr;
        while (cur) {
            ListNode* post = cur->next;
            cur->next = prev;
            prev = cur;
            cur = post;
        }
        return prev;
    }
};