面试题 02.05

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

Example:

Input: (7 -> 1 -> 6) + (5 -> 9 -> 2). That is, 617 + 295. Output: 2 -> 1 -> 9. That is, 912. Follow Up: Suppose the digits are stored in forward order. Repeat the above problem.

Example:

Input: (6 -> 1 -> 7) + (2 -> 9 -> 5). That is, 617 + 295. Output: 9 -> 1 -> 2. That is, 912.

Solutions

1. simulation

2. the traversal order is the same as the order when we add up digits by hands;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode * cur = nullptr, * head = nullptr;
        int remain = 0;
        while (l1 || l2 || remain) {
            remain += l1 ? l1->val : 0;
            remain += l2 ? l2->val : 0;
            l1 = l1 ? l1->next : nullptr;
            l2 = l2 ? l2->next : nullptr;
            ListNode* pnode = new ListNode(remain % 10);
            if (!head) head = pnode;
            if (cur) cur->next = pnode;
            cur = pnode;
            remain /= 10;
        }

        return head;
    }
};