https://leetcode.com/problems/add-two-numbers/

Solution

As the head of list is the last digit of the number, we can add 2 lists by iterating from heads of 2 lists.

The only thing to note is remember to handle the longer list after reach the tail of one list.

Runtime: O(n). n is the size of longer list.

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;
        ListNode* head = new ListNode(0);
        ListNode* cur = head;

        while (l1 && l2) {
            int sum = (carry + l1->val + l2->val) % 10;
            carry = (carry + l1->val + l2->val) / 10;
            cur->next = new ListNode(sum);
            cur = cur->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        ListNode* l;
        if (l1) l = l1; else if (l2) l = l2;
        if (l) {
            while (l) {
                int sum = (carry + l->val) % 10;
                carry = (carry + l->val) / 10;
                cur->next = new ListNode(sum);
                        cur = cur->next;
                        l = l->next;
            }
            if (carry != 0) cur->next = new ListNode(carry);
            return head->next;
        }
        if (carry != 0) cur->next = new ListNode(carry);
        return head->next;
    }

What can we learn from this simple question: as the question requires us to return head of the result list. We can do is as following:

    ListNode* head = new ListNode(0);
    ListNode* cur = head;
    ...
    return head->next;