Given the reference (pointer) to the head node of a linked list.
A number is represented by this linked list such that each digit corresponds to a node in it.
The task is to add "1" to it and return the result in a linked list representation such that each digit is represented by one node.
Input: 9->9->9->null
Output: 1->0->0->0
Input: 1->2->3->null
Output: 1->2->4->null
Solutions
Method 1: Iterative
Below are the steps :
Reverse the given linked list.
Start traversing the linked list from the head node and add 1 to it.
Keep moving to the next node until carry is greater than "1" and the linked list is not exhausted.
Once the linked list is exhausted and the carry is still greater than "1", we need to add one new node to store this digit.
Reverse the linked list again.
Complexity
The time complexity of this solution is O(n) and space complexity is O(1).