Add One to Linked List

Easy
0/40
Average time to solve is 10m
profile
Contributed by
26 upvotes
Asked in companies
UberSamsung R&D InstitutePayPal

Problem statement

Ninja has been given a number that is represented in the form of a linked list such that each digit corresponds to a node. He has been asked to add 1 to it and return the updated list.

For Example:

1234 is represented as (1 -> 2 -> 3 -> 4) and adding 1 to it should change it to (1 -> 2 -> 3 -> 5).

Note:

The input Linked list does not have any trailing zeros.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains ‘N’ space-separated integers denoting the nodes of the Linked List. Here, ‘-1’ will be present at the end of each test case denoting the termination of the linked list.
Output Format: 
For each case, we need to return the updated linked list where each node will be separated by a space. 

The output of each test case will be printed in a separate line.
Note: 
You do not need to input or print anything, and it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N <= 10000
0 <= |nodeValue| <= 9

Where ‘N’ denotes the size of the linked list.

Time Limit: 1 sec
Sample Input 1:
1 
4 2 9 -1
Sample Output 1:
4 3 0 -1
Explanation of Sample Input 1:
Test case 1:
For the first test case of sample output 1, our input number is ‘429’. On adding ‘1’ to it, we get output as ‘430’.
Sample Input 2:
2 
9 -1
9 5 6 5 4 3 5 -1
Sample Output 2:
1 0 -1
9 5 6 5 4 3 6 -1
Explanation of Sample Input 2:
Test case 1:
For the first test case of sample output 2, our given input is ‘9’. On adding 1 to it, we get ‘10’ for which we will have to create a new node and the number of digits has increased from ‘1’ to’2’.
Hint

Will reversing the list help??

Approaches (1)
Greedy Approach

Here, the number is represented from left to right but while adding one, we need to travel the number from right to left. Firstly, we need to reverse the list, then we will add 1 to the first digit and maintain a variable carry which will to added to the second digit if required and this process goes on. Finally, once our addition is done, we can reverse the list again and return the head.

 

Algorithm:

 

  • Declare a local node pointer variable ‘end’ which will hold the last node of the list i.e. ‘-1’ and we will remove this node from the list for the time being.
  • Declare a function that reverses the LinkedList, and reverse the LinkedList ‘head’.
  • Declare a node pointer ‘prev’ and initialize it with ‘NULL’ and set temp to head
  • Run a while loop which will terminate either ‘temp’ reaches the end of the list or we encounter a digit less than ‘9’
    • Till then, update the value of ‘temp’ with ‘0’
    • Set ‘prev’ to ‘temp’ and shift ‘temp’ to right
  • If the loop terminates for encountering a digit less than ‘9’
    • Increase the digit by 1
  • Otherwise, the loop has terminated for reaching the end of the list
    • Hence, we need to add a new node to the next of ‘prev’ with value ‘1’
  • Reverse the list again
  • Add ‘end’ at the of the list
  • Return head.

 

 

Description of Reverse function:

 

  • If our current head is NULL, return NULL
  • If our list has just one node, return that node.
  • Declare three local node pointers as ‘prev’, ‘temp’, and ‘current’ and initialize them with ‘NULL’, ‘head’, and ‘NULL’ respectively.
  • Run a while loop which will terminate when ‘temp’ reaches the end of the list
    • Update ‘current’ as ‘temp’
    • Shift temp to the next node
    • Change the pointer of ‘current’ to ‘prev’
    • Update ‘prev’ with ‘current’
  • Update ‘head’ with ‘prev’
  • Return head
Time Complexity

O(N ) where 'N' is the length of the LinkedList.

 

As we are traversing through the list four to five times just, so our time complexity is O(N).

Space Complexity

O(1)

 

Constant space is used.

Code Solution
(100% EXP penalty)
Add One to Linked List
Full screen
Console