Double a Number Represented as a Linked List Leetcode Solution

Problem Statement

LeetCode Question Link

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.

• Solution
  • Algorithm steps:
  • Time complexity:
  • Space complexity:
  • Complexity reduction:
  • Modified Code
  • Algorithm steps:
  • Time complexity:
  • Space complexity:

Solution

// Class definition for Solution.
class Solution { 
public:
  // Definition of member function doubleIt taking a pointer to ListNode head as argument and returning a pointer to ListNode.
  ListNode* doubleIt(ListNode* head) 
  { 
    // Check if the value of head node is greater than or equal to 5.
    if (head->val >= 5) 
      // If true, create a new ListNode with value 0 and head as its next node.
      head = new ListNode(0, head); 

    // Loop through the linked list starting from head node.
    for (ListNode* curr = head; curr != nullptr; curr = curr->next) 
    { 
      // Double the value of current node.
      curr->val *= 2; 
      // Take modulo 10 of current node's value.
      curr->val %= 10; 
      // Check if there is a next node and its value is greater than or equal to 5.
      if (curr->next && curr->next->val >= 5) 
        // If true, increment the value of current node.
        ++curr->val; 
    }
    // Return the modified head node.
    return head; 
  }
};

Algorithm steps:

1. Check if the value of the head node is greater than or equal to 5.
2. If true, insert a new node with value 0 before the current head node.
3. Traverse through the linked list from the head node.
4. Double the value of each node.
5. Take modulo 10 of each node's value.
6. If there is a next node and its value is greater than or equal to 5, increment the current node's value.
7. Repeat steps 3 to 6 until all nodes are processed.
8. Return the modified head node.

Time complexity:

• The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. This is because the algorithm traverses through all the nodes once.

Space complexity:

• The space complexity of this algorithm is O(1), as it does not use any extra space proportional to the size of the input. It only modifies the existing linked list in-place.

Complexity reduction:

• The time complexity of the given algorithm is already optimal for performing the required operations on the linked list. However, the space complexity can be reduced by avoiding the creation of a new node when the value of the head node is greater than or equal to 5. Here's the modified code:

Modified Code

This modification ensures that we don't create a new node unnecessarily at the beginning of the linked list if it's not required. The time complexity remains the same, O(n), but the space complexity remains O(1) as well, with no additional space used.

class Solution {
public:
  // Definition of a member function doubleIt taking a pointer to ListNode head as argument and returning a pointer to ListNode.
  ListNode* doubleIt(ListNode* head) 
  { 
    // Loop through the linked list starting from head node.
    for (ListNode* curr = head; curr != nullptr; curr = curr->next) 
    { 
      // Double the value of current node.
      curr->val *= 2; 
      // Take modulo 10 of current node's value.
      curr->val %= 10; 
      // Check if there is a next node and its value is greater than or equal to 5.
      if (curr->next && curr->next->val >= 5) 
        // If true, increment the value of current node.
        ++curr->val; 
    }

    // Check if the value of the head node is greater than or equal to 5.
    if (head->val >= 5) 
      // If true, insert a new node with value 0 before the current head node.
      head = new ListNode(0, head); 

    // Return the modified head node.
    return head; 
  }
};

Algorithm steps:

1. Traverse through the linked list from the head node.
2. Double the value of each node.
3. Take modulo 10 of each node's value.
4. If there is a next node and its value is greater than or equal to 5, increment the current node's value.
5. Repeat steps 1 to 4 until all nodes are processed.
6. Check if the value of the head node is greater than or equal to 5.
7. If true, insert a new node with value 0 before the current head node.
8. Return the modified head node.

Time complexity:

• The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. This is because the algorithm traverses through all the nodes once.

Space complexity:

• The space complexity of this algorithm is O(1), as it does not use any extra space proportional to the size of the input. It only modifies the existing linked list in-place.

The complexity seems optimal, so there's no need for further reduction.