#2816

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Double a Number Represented as a Linked List

Double a number represented as a linked list by carefully managing node values and carries with pointer traversal techniques.

linked list math stack

Problem Statement

You are given the head of a non-empty singly linked list representing a non-negative integer. Each node contains a single digit, and the digits are stored in forward order, meaning the head node represents the most significant digit. Your task is to return the head of the linked list after doubling the integer it represents, maintaining the same node structure.

For example, given the linked list [1,8,9], which represents the number 189, the doubled value is 378, so the returned linked list should be [3,7,8]. You must handle carry-over properly for digits that sum to 10 or more, such as in [9,9,9], which doubles to [1,9,9,8]. Constraints include 1 <= number of nodes <= 104 and each node value between 0 and 9, with no leading zeros except for the number 0 itself.

Examples

Example 1

Input: head = [1,8,9]

Output: [3,7,8]

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]

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.

Solution Approach

Reverse the Linked List

Reverse the linked list to start from the least significant digit, making it easier to propagate carry while doubling each node.

Double Each Node and Handle Carry

Iterate through the reversed list, multiply each node's value by 2, and manage the carry to the next node. Append a new node if carry remains after the last node.

Restore Original Order

Reverse the linked list again to restore the original most-significant-first order, ensuring the output represents the correct doubled number.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) since each node is visited twice during reversal and doubling. Space complexity is O(1) because all operations are in-place without extra data structures.

What Interviewers Usually Probe

Check if candidate reverses the list to simplify least-significant-digit manipulation.
Watch for correct carry propagation across multiple nodes, especially consecutive 9s.
Notice if candidate maintains O(1) space by avoiding extra stacks or arrays.

Common Pitfalls or Variants

Common pitfalls

Failing to reverse the linked list first can complicate carry handling.
Forgetting to add an extra node when a carry remains after the last node.
Incorrectly assuming the list is in least-significant-digit-first order, leading to wrong results.

Follow-up variants

Doubles a number stored in a linked list in reverse order without reversing the list.
Triple the number represented by the linked list instead of doubling.
Perform addition of two numbers represented by linked lists using similar pointer traversal.

FAQ

How do I handle the carry when doubling a number in a linked list?

Traverse from the least significant digit, double each node's value, and propagate any carry to the next node, adding a new node if needed.

Do I need extra space to double a linked list number?

No, you can perform all operations in-place using pointer manipulation and reversing the list.

Why reverse the linked list before doubling?

Reversing makes it easier to start from the least significant digit and correctly propagate carry without recursion or a stack.

How does GhostInterview approach the 'Linked-list pointer manipulation' pattern?

It guides you through careful node updates and carry handling step-by-step, ensuring correctness and efficiency.

What happens if the list contains multiple 9s?

GhostInterview ensures carry is properly added across all 9s, and a new node is appended if the final carry is non-zero.

terminal

Solution

Solution 1: Reverse Linked List + Simulation

First, we reverse the linked list, then simulate the multiplication operation, and finally reverse the linked list back.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(head):
            dummy = ListNode()
            cur = head
            while cur:
                next = cur.next
                cur.next = dummy.next
                dummy.next = cur
                cur = next
            return dummy.next

        head = reverse(head)
        dummy = cur = ListNode()
        mul, carry = 2, 0
        while head:
            x = head.val * mul + carry
            carry = x // 10
            cur.next = ListNode(x % 10)
            cur = cur.next
            head = head.next
        if carry:
            cur.next = ListNode(carry)
        return reverse(dummy.next)

Continue Practicing

#2818 apply operations to maximize score #2807 insert greatest common divisors in linked list #2487 remove nodes from linked list