Add one to a number represented as Linked List

Easy
0/40
Average time to solve is 23m
135 upvotes
Asked in companies
Josh Technology GroupPark+

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
3
1 5 2


Sample Output 1:
1 5 3


Explanation For Sample Input 1:
Initially the number is 152. After incrementing it by 1, the number becomes 153.


Sample Input 2:
2
9 9


Sample Output 2:
1 0 0


Explanation For Sample Input 2:
Initially the number is 9. After incrementing it by 1, the number becomes 100. Please note that there were 2 nodes in the initial linked list, but there are three nodes in the sum linked list.


Expected time complexity :
The expected time complexity is O('n').


Constraints:
1 <= 'n' <=  10^5
0 <= Node in linked list <= 9

There are no leading zeroes in the number.

Time Limit: 1 sec
Hint

Try to reach the last node of the linked list using recursion.

Approaches (2)
Recursive Approach

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.
Time Complexity

O(n), Where 'n' is the length of the number we're given in the form of a linked list.

We are traversing the entire list exactly once, making the time complexity asymptotic to the length of the linked list.

Hence the time complexity is O(n).

Space Complexity

O(n), Where 'n' is the length of the number we're given in the form of a linked list.

We are solving the problem recursively, and there will be recursive states equal to the number of nodes.

Hence the space complexity is O(n).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Add one to a number represented as Linked List
Full screen
Console