2816

2816. Double a Number Represented as a Linked List (Medium)

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.

 

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, 104]
• 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.

Companies: Amazon

Related Topics:
Linked List, Math, Stack

Similar Questions:

• Add Two Numbers (Medium)
• Plus One Linked List (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/double-a-number-represented-as-a-linked-list
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
    ListNode *reverseList(ListNode *head) {
        ListNode dummy;
        while (head) {
            auto p = head;
            head = head->next;
            p->next = dummy.next;
            dummy.next = p;
        }
        return dummy.next;
    }
public:
    ListNode* doubleIt(ListNode* head) {
        head = reverseList(head);
        int carry = 0;
        ListNode *prev = nullptr;
        for (auto p = head; p; ) {
            carry += p->val * 2;
            p->val = carry % 10;
            carry /= 10;
            prev = p;
            p = p->next;
        }
        if (carry) prev->next = new ListNode(carry);
        return reverseList(head);
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/double-a-number-represented-as-a-linked-list
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* doubleIt(ListNode* head) {
        ListNode *prev = nullptr;
        for (auto p = head; p; ) {
            int n = p->val * 2;
            if (n / 10) {
                if (prev) prev->val++;
                else {
                    auto h = new ListNode(1);
                    h->next = head;
                    head = h;
                }
            }
            p->val = n % 10;
            prev = p;
            p = p->next;
        }
        return head;
    }
};