Scale Engineer

Double a Number Represented as a Linked List

Med
#2520Time: O(N^2), where N is the number of nodes. Building the `BigInteger` involves multiplications that take time proportional to the number of digits, leading to a quadratic time complexity.Space: O(N), where N is the number of nodes. This space is used to store the `BigInteger` representation, its string form, and the new linked list.1 company
Patterns
Math
Data structures
Linked ListStack
Companies
Nvidia

Prompt

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.

Approaches

4 approaches with complexity analysis and trade-offs.

This approach converts the linked list representation of the number into a BigInteger, doubles it, and then converts the result back into a new linked list. It's conceptually simple but very inefficient for large numbers due to the overhead of BigInteger operations, making it impractical for the given constraints.

Algorithm

  • Initialize a BigInteger variable number to zero.
  • Traverse the linked list from the head.
  • In each step, update the number by the formula: number = number * 10 + node.val.
  • After the traversal, multiply the number by 2.
  • Convert the resulting BigInteger to its string representation.
  • Create a new dummy head for the result list.
  • Iterate through the characters of the string, create a new ListNode for each digit, and append it to the result list.
  • Return the next node of the dummy head.

Walkthrough

The most straightforward way to approach this problem is to treat it as a standard arithmetic problem. We first convert the linked list, which represents the number digit by digit, into an actual integer data type. Since the number of digits can be up to 10,000, we must use a data type that supports arbitrary-precision arithmetic, such as Java's BigInteger.

Once the number is in BigInteger form, we can simply multiply it by two. The final step is to convert this doubled number back into a linked list. We can do this by first converting the BigInteger to a string, and then creating a new linked list where each node corresponds to a digit in the string.

import java.math.BigInteger; /** * 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) {        if (head == null) {            return null;        }         // 1. Convert list to BigInteger        BigInteger number = BigInteger.ZERO;        ListNode current = head;        while (current != null) {            number = number.multiply(BigInteger.TEN).add(BigInteger.valueOf(current.val));            current = current.next;        }         // 2. Double the number        number = number.multiply(BigInteger.valueOf(2));         // 3. Convert back to linked list        String s = number.toString();        ListNode newHead = new ListNode(0);        ListNode tail = newHead;        for (char c : s.toCharArray()) {            tail.next = new ListNode(c - '0');            tail = tail.next;        }         return newHead.next;    }}

Complexity

Time

O(N^2), where N is the number of nodes. Building the `BigInteger` involves multiplications that take time proportional to the number of digits, leading to a quadratic time complexity.

Space

O(N), where N is the number of nodes. This space is used to store the `BigInteger` representation, its string form, and the new linked list.

Trade-offs

Pros

  • The logic is very simple and easy to understand.

  • It leverages powerful, built-in libraries for handling large numbers.

Cons

  • Highly inefficient with a time complexity of O(N^2) due to repeated BigInteger multiplications.

  • The constraints of the problem (up to 10^4 nodes) make standard integer types like long overflow, necessitating the use of a BigInteger library which might not be desirable or available.

Solutions

/** * 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 ) { head = reverse ( head ); ListNode dummy = new ListNode (); ListNode cur = dummy ; int mul = 2 , carry = 0 ; while ( head != null ) { int x = head . val * mul + carry ; carry = x / 10 ; cur . next = new ListNode ( x % 10 ); cur = cur . next ; head = head . next ; } if ( carry > 0 ) { cur . next = new ListNode ( carry ); } return reverse ( dummy . next ); } private ListNode reverse ( ListNode head ) { ListNode dummy = new ListNode (); ListNode cur = head ; while ( cur != null ) { ListNode next = cur . next ; cur . next = dummy . next ; dummy . next = cur ; cur = next ; } return dummy . next ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem