Problem Statement

Given the head of a singly linked list representing a positive integer number. Each node of the linked list represents a digit of the number, with the 1st node containing the leftmost digit of the number and so on. The task is to add one to the value represented by the linked list and return the head of a linked list containing the final value.

The number will contain no leading zeroes except when the value represented is zero itself.

Examples

Example 1:
Input: 1->2->3
Output: 1->2->4

Explanation: The number represented by the linked list = 123
123 + 1 = 124

Example 2:

Input: 9->9
Output: 1->0->0

Explanation: The number represented by the linked list = 99
99 + 1 = 100

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Imagine you have a number represented as a linked list, where each node contains a single digit. The first node contains the leftmost digit. Our goal is to add one to this number. This might sound simple, but we need to handle the digit carry-over, just like we do when adding numbers manually. Starting from the rightmost digit makes it easier to manage carry-overs. However, since our linked list starts from the leftmost digit, we need to reverse the list first. This makes it easier to add one from the least significant digit and manage any carry-over.

Approach:

1. Reverse the Linked List: Reverse the linked list so we can start the addition from the rightmost digit.
2. Add One: Add one to the first digit of the reversed list. If there’s a carry (result is 10), set the current digit to 0 and carry over 1 to the next digit.
3. Handle the Carry: If there’s still a carry after reaching the end of the list, add a new node with the digit 1.
4. Reverse Again: Reverse the list again to restore the original order, now with the added value.
5. Return the New Head: Return the head of the modified linked list.

Code:

Complexity Analysis:

• Time Complexity: O(N) because we traverse the linked list three times, each with a time complexity of O(N), resulting in O(3N), which simplifies to O(N) since constant factors are ignored in Big-O notation. Here, N is the number of nodes in the linked list.
• Space Complexity: O(1) because we use a constant amount of extra space for pointers and variables.