Problem Statement

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<sup>4</sup>]

• 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.

Intuition

In this question there are two tricky parts:

• How to traverse the LinkedList.

• How to handle the carry-over number after multiplication.

How to traverse the LinkedList?

In order to multiply a number we start with its least significant digit and move towards the most significant digit. In this problem we're given the head of LinkedList. The head of LinkedList will have the most significant digit of that number. So, how do we traverse the LinkedList?

What if we reverse the LinkedList and then traverse it? In that way we will have the least significant digit as the head. Then we just need to traverse the LinkedList as usual.

We can follow two approach to reverse the LinkedList:

• Reversing using a helper function, in which we pass the head of LinkedList. The function returns a new head of reversed LinkedList.

• Using a stack to store nodes and then pop() the nodes.

How to handle the carry-over number after multiplication?

When we multiply any digit greater than or equal to 5 we will get a carry-over number that should be added to the next number after it is multiplied.

We can easily find the carry by doing a numeric division of the multiplied number by 10.

For example: if the number is 7, the 7*2=14. We can find the value of node by doing 14%10=4 and carry-over number by 14//10=1. This 1 will then be added to the next multiplied number.

Code Solution

Reversing and then Re-reversing LinkedList

Python Code:

# 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]:
        # reverse the linkedlist
        reversed_head=self.reverseLinkedList(head)
        # initialize a variable for carry
        carry=0
        # intialize curr_node to head of reversed linkedlist
        # prev_node to None
        curr_node,prev_node=reversed_head,None
        while curr_node:
            # multiply current node's value by 2 and adding the previous carry
            multiplied=2*curr_node.val+carry
            # the last digit will be the value of curr_node
            curr_node.val=multiplied%10
            # Update carry for the next iteration
            carry = 1 if multiplied > 9 else 0
            # Move to the next node
            prev_node, curr_node = curr_node, curr_node.next
        # If there's a carry after the loop, add an extra node
        if carry:
            prev_node.next = ListNode(carry)
        # Reverse the list again to get the original order
        result = self.reverseLinkedList(reversed_head)
        return result

    def reverseLinkedList(self, head:Optional[ListNode])-> Optional[ListNode]:
        curr_node,prev_node=head,None
        while curr_node:
            # Store the next node
            next_node = curr_node.next
            # Reverse the link
            curr_node.next = prev_node
            # Move to the next nodes
            prev_node, curr_node = curr_node, next_node
        return prev_node

Reversing LinkedList using Stack

Python Code:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# TC: O(n)
# SC: O(n)
class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # initialize the stack(it is just an array)
        stack=[]
        # initialize a local variable to keep head preserved
        curr_node=head
        # iterate till end of linkedlist
        while curr_node:
            # keep appending to stack
            stack.append(curr_node)
            # move to next node
            curr_node=curr_node.next
        # initialize a local variable to remake the linkedlist 
        tail_node=None
        # this will be used for doubling
        num=0
        # iterate till there are values in stack and num is not zero
        while stack or num!=0:
            # initialize tail with zero value and previous tail_node as next
            # basically making the linkedlist again
            tail_node=ListNode(0,tail_node)
            # if there are values in stack
            if stack:
                # pop the value
                # multiply by 2
                # and add the last carry
                num+=stack.pop().val*2
            # assign least significant digit to value of tail_node
            tail_node.val=num%10
            # find the carry
            # it will be the most significant digit
            num//=10
        # return tail_node as now tail_node is the head of re-constructed linkedlist
        return tail_node

Time and Space Complexity

Reversing and then Re-reversing LinkedList

Time Complexity:

$$O(n)$$

As we're iterating over the LinkedList at least once.

Space Complexity:

$$O(1)$$

As we're not allocating any more space.

Reversing LinkedList Using Stack

Time Complexity:

$$O(n)$$

As we're iterating over the LinkedList at least once.

Space Complexity:

$$O(n)$$

As we're allocating extra space for stack.

Conclusion

In this problem we get to learn two ways to solve this problem:

• Reversing and then Re-reversing

• Reversing LinkedList using Stack

Hope that explanation made sense and you found this blog helpful. If you've made it this far, please give it a like and drop a comment.

Happy Coding!🚀