2871. Double A Number Represented As A Linked List¶

Difficulty: Medium

2871. 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, 10⁴]
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.

Solution¶

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode doubleIt(ListNode head) {
        String current = "";
        ListNode temp = head;
        while (temp != null) {
            current += temp.val;
            temp = temp.next;
        }
        String dummy = current, res = "";
        int carry = 0;
        for (int i = current.length() - 1; i >= 0; i--) {
            int first = current.charAt(i) - '0';
            int second = dummy.charAt(i) - '0';
            int dig = first + second + carry;
            if (i == 0) {
                res = dig + (res);
                continue;
            }
            if (dig >= 10) {
                res = (dig % 10) + res;
                carry = dig / 10;
            }
            else {
                res = dig + res;
                carry = 0;
            }
        }

        ListNode answer_node = null;
        for (int i = res.length() - 1; i >= 0; i--) {
            int current_data = res.charAt(i) - '0';
            answer_node = insert(answer_node, current_data);
        }
        return answer_node;
    }

    private ListNode insert(ListNode head, int data) {
        ListNode to_insert = new ListNode(data);
        if (head == null) return new ListNode(data);
        to_insert.next = head;
        head = to_insert;
        return head;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here