1. Add Two Numbers You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

S：dummy node

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* before = &dummy;
        int carry = 0;
        while(l1 || l2 || carry){
            int sum = carry + (l1?l1->val:0) + (l2?l2->val:0);
            carry = sum/10;
            before->next = new ListNode(sum%10);
            before = before->next;
            if(l1) l1 = l1->next;
            if(l2) l2 = l2->next;
        }
        return dummy.next;
    }

369. Plus One Linked List

Given a non-negative integer represented asnon-emptya singly linked list of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

Example:

Input:
1->2->3

Output:
1->2->4

S: reverse O(n)

反转list然后加一

    ListNode* plusOne(ListNode* head) {
        if (!head) return head;
        ListNode* tail = reverseNode(head);
        int carry = 1;
        ListNode* node = tail;
        while (node) {
            int sum = node->val + carry;
            node->val = sum % 10;
            carry = sum / 10;
            node = node->next;
        }
        if (carry == 1) {
            head->next = new ListNode(1);
        }
        return reverseNode(tail);
    }

    ListNode* reverseNode(ListNode* node) {
        ListNode* pre = nullptr;
        ListNode* next = nullptr;
        while(node) {
            next = node->next;
            node->next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }