Last Updated: 7 Dec, 2020
Add one to a number represented as Linked List
Easy
Asked in companies
You're given a positive integer represented in the form of a singly linked-list of digits. The length of the number is 'n'.
Add 1 to the number, i.e., increment the given number by one.
The digits are stored such that the most significant digit is at the head of the linked list and the least significant digit is at the tail of the linked list.
Example:
Input: Initial Linked List: 1 -> 5 -> 2
Output: Modified Linked List: 1 -> 5 -> 3
Explanation: Initially the number is 152. After incrementing it by 1, the number becomes 153.
Input Format:
The first line contains an integer 'n', the length of the number / the length of the linked list.
The second line contains 'n' space separated integers denoting the digits of the number / the nodes of the linked list.
Output Format:
Print space - separated integers denoting the nodes of the output linked list.
Note :
You do not need to print anything. You're given the head of the linked list, return the head of the modified list.
Approaches
In this approach, we will use recursion to add 1 to the linked list. We can recursively reach the last node, add 1 to it and forward the carry to the previous node.
This solution does not require reversing the linked list.
The steps are as follows:
Node *addOne(Node *‘head’)
- Remove the leading zeroes by deleting the starting nodes with data value 0.
- Let “addOneHelper” be the recursive function that takes the head of the linked list and returns the carry value given by the head node after adding 1.
- If the head is NULL, return 1.
- Find the carry obtained from the next node by recursively calling the function for the next node of the head.
- Store the sum of the carry obtained from the next node and the current node’s data in a variable ‘res.’
- Store res%10 in the current node’s data.
- Return res/10.
- After adding carry up to the first node of the list, if the value of carry is still non-zero, append a new node with its value at the beginning of the resultant linked list.
- Return the head of the resultant linked list.
The basic idea is to reverse the given list to make addition easier.
We will maintain a variable ‘carry’ with an initial value ‘1’ as we have to add 1 to the given number.
Now we will traverse the list from the least significant digit, which is at the starting of the reversed list, and for each digit, we will add ‘carry’ to it.
The steps are as follows:
Node *addOne(Node *‘head’)
- Remove the leading zeros from the list.
- Reverse the given linked list.
- Take a variable ‘carry’ (with initial value 1).
- Traverse the reversed list from starting to the end and for each node, perform the following steps.
- Store sum of ‘carry’ and current node’s data in a variable ‘sum’.
- Store sum/10 in ‘carry’. (For e.g., If the sum is 18, then 18/10 i.e. 1, will be the carry).
- Store sum%10 to current node’s data.
- If ‘carry’ is not zero
- Add a new node at the end of the list with the data value ‘carry’.
- Reverse the linked list to get the desired output.