2816. Double a Number Represented as a Linked List

Description

You are given the head of a non-empty linked list representing a non-negative integer without leading zeroes.

Return the head of the linked list after doubling it.

Examples

Example 1:

Input: head = [1,8,9]
Output: [3,7,8]
Explanation: The figure above corresponds to the given linked list which represents the number 189. Hence, the returned linked list represents the number 189 * 2 = 378.

Example 2:

Input: head = [9,9,9]
Output: [1,9,9,8]
Explanation: The figure above corresponds to the given linked list which represents the number 999. Hence, the returned linked list reprersents the number 999 * 2 = 1998.

Constraints:

• The number of nodes in the list is in the range [1, 10^4]
• 0 <= Node.val <= 9
• The input is generated such that the list represents a number that does not have leading zeros, except the number 0 itself.

C++

先做一次 reverse 將鍊結串列翻轉過來，會達成從低位數到高位數的排列，我們用此順序做乘法，並使用一個 carry 紀錄進位，若是最後一個節點尚有 carry，則新增一個節點。

class Solution {
public:
    ListNode* reverse(ListNode* head) {
        ListNode* prev = NULL;
        ListNode* temp;
        while (head != NULL) {
            temp = head->next;
            head->next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
    ListNode* doubleIt(ListNode* head) {
        head = reverse(head);
        int carry = 0;
        ListNode* tmp = head;
        while (tmp) {
            tmp->val *= 2;
            tmp->val += carry;
            carry = tmp->val / 10;
            tmp->val %= 10;
            if (!tmp->next)
                break;
            tmp = tmp->next;
        }
        if (carry) {
            ListNode* n = new ListNode(carry);
            tmp->next = n;
        }
        return reverse(head);
    }
};