Add 1 to a number represented as linked list {optimized solution by keeping track of carry and null pointer exception}🔗➕1️⃣(GFG)

Day 8 of Solving DSA Problems

PROBLEM LINK : Add 1 to a number represented as linked list (GeeksForGeeks Medium)

❓PROBLEM STATEMENT

A number N is represented in Linked List such that each digit corresponds to a node in linked list. You need to add 1 to it.

Example 1:

Input:
LinkedList: 4->5->6
Output: 457
Explanation: 4->5->6 represents 456 and when 1 is added it becomes 457. 
        

Example 2:

Input:
LinkedList: 1->2->3
Output: 124         

Your Task: Your task is to complete the function addOne() which takes the head of the linked list as the only argument and returns the head of the modified linked list. The driver code prints the number. Note: The head represents the left-most digit of the number.

Expected Time Complexity: O(N). Expected Auxiliary Space: O(1).

Constraints: 1 <= N <= 1021

🤔INTUITION

Now, I know what you are thinking that if we have to add 1 to it then why don't we just simply traverse to the last value of the linked list and then add one to it and return the head and peace✌🏻but that's not the case my friend, but before explaining why is that I would like you to think about three possible Types of test cases for this question:

Type1 : Every Element in not equal to 9

Input:
LinkedList: 2->3->1->4
Output: 2315         

Type 2: One or More than one (not all) elements are equal to 9

Input:
LinkedList: 2->3->9->9
Output: 2400         

Type 3: All the elements are equal to 9

Input:
LinkedList: 9->9->9->9->
Output: 10000         

Now, why is 9 so Important here. Take a Look at the 2nd and 3rd test case carefully. In second test case, the last non 9 element is increasing where as in place of all the 9s we are getting 0. whereas in the third test case, all the 9 elements are getting 0 and a 1 is added at the front. Hence one thing is clear that we have to consider whole List as one digit and not only the last element.

In order to do the addition we have to start adding from the last (just like we used to do as a kid) and to take care of the carry we have to keep track of all the 9s and non 9 elements.

Algorithm:

STEP 1: Reverse the List (You can do it using either three pointers or stack)

STEP 2: Do the Addition, handle the carry and Null pointer Exception

STEP 3: Reverse the List again and return it

🧑🏻💻CODE

class Node:
    def __init__(self, data):   # data -> value stored in node
        self.data = data
        self.next = None

class Solution:
    def addOne(self,head):
        
# STEP 1
        prev = None
        current = head

        while current is not None:
            next_node = current.next

            current.next = prev

            prev = current
            current = next_node

        head = prev
        
# STEP 2
        current = head 

        if current.data != 9:
            current.data += 1

        else:
            while current.data == 9 and current.next: 
                current.data = 0
                current = current.next
            current.data += 1 
        
# STEP 3 
        prev = None
        current = head

        while current is not None:
            next_node = current.next

            current.next = prev

            prev = current
            current = next_node

        result_head = prev
        
        return result_head        

📝APPROACH

1. Reverse the Linked List: The code first reverses the linked list. This is done to simplify the addition process since the least significant digit is at the beginning of the reversed list.After this step, head now points to the reversed linked list.
2. Add 1 and Handle Carry: The code then iterates through the reversed linked list, starting from the least significant digit. If the current digit is not 9, it simply adds 1 to it. If the current digit is 9, it sets it to 0 and continues to the next digit. If a carry is still needed after iterating through all the digits, a new node with value 1 is added to the end of the linked list.
3. Reverse the Linked List Again: Finally, the code reverses the linked list again to bring it back to its original order.The result_head now points to the updated linked list with 1 added to the original number.
4. Return Result: The code returns the result_head, which is the head of the modified linked list.

This approach effectively adds 1 to the number represented by the linked list while handling carries and preserving the order of digits.

⌛COMPLEXITY ANALYSIS

Time Complexity:

• Reversing the Linked List: This step has a time complexity of O(n), where n is the number of nodes in the linked list.
• Adding 1 and Handling Carry: This step also has a time complexity of O(n) because it iterates through the linked list once.
• Reversing the Linked List Again: Similar to the first step, this has a time complexity of O(n).

Overall, the time complexity of the code is dominated by the three linear passes through the linked list. Therefore, the total time complexity is O(n).

Space Complexity:

The space complexity of the code is determined by the space used for variables and the space needed for the reversed linked list. Here are the major contributors to the space complexity:

• Variables: The code uses a constant amount of additional space for variables like prev, current, next_node, and result_head. Therefore, the space complexity due to variables is O(1).
• Reversed Linked List: The code reverses the linked list in-place, which means it doesn't create a new linked list. It uses the existing nodes to reverse the order. So, the space complexity for the reversed linked list is O(1) because it doesn't depend on the input size.

Overall, the space complexity of the code is O(1) because it doesn't use additional memory that scales with the input size, except for a constant amount of space for variables.

🔟ALTERNATE APPROACH(From GFG Editorial)

💡Intuition

The idea is that by reversing the linked list, we can start from the least significant digit and propagate the carry (if any) during the addition operation. If the carry still exists at the end of the list traversal, we add an additional node to represent the carried digit.

🧑🏻💻Implementation

1. Reverse Method: This method takes a Node representing the head of a linked list as input and reverses the order of the linked list. It uses a classic iterative approach to reverse the list. It maintains three pointers: prev, current, and next.The loop continues until current becomes null.Inside the loop, the next pointer is used to temporarily store the reference to the next node, then the current. next pointer is redirected to point to the previous node (prev), and finally, prev and current are updated to move forward in the list.After the loop, the method returns the new head of the reversed linked list, which is the last node visited (prev).
2. addOne Method: This method takes a linked list representing a non-negative integer (each node contains a digit of the integer) and adds one to the integer.The method first reverses the linked list using the reverse method to simplify the addition process. Reversing the list makes it easier to process digits from right to left. It initializes a carry variable to 1, which represents the value to be added.The method then iterates through the reversed list, adding 1 to the value of each node's data.If the resulting value is less than 10, the method immediately reverses the list back and returns it.If the value becomes 10 or more, the data of the current node is set to 0, and the carry is propagated to the next iteration.If the end of the list is reached and there is still a carry, a new node with a value of 1 is added to the end of the list to represent the carried digit.Finally, the method reverses the list again and returns the new head.

class Solution:    
    def reverse(self,head):
    # this function reverses the linked list
        prev = None
        current = head
        next = head.next
        
        while current is not None:
            next = current.next       # storing next node
            current.next = prev       # linking current node to previous
            prev = current            # updating prev
            current = next            # updating current
        
        return prev
    
    def addOne(self,head):
        head = self.reverse(head)   # reversing list to make addition easy
        
        current = head
        carry = 1
        
        while(carry):
            current.data += 1         # adding one to current node
            
            if current.data < 10:
                return self.reverse(head)
                # if no carry we can reverse back list and return it
            else:
                current.data = 0
                # else we continue with taking carry forward
            
            if current.next is None:
                break
                # if end of list, we break from loop
            else:
                current = current.next
                # else we move to next node
        
        current.next = Node(1)        # adding new node for the carried 1
        return self.reverse(head)        

⌛Complexity 

Time complexity : O(n),As we make three passes, two for reversing the list and one for adding, where N is the total number of nodes in the linked list.

Space complexity:  O(1), This will not cost any memory space.