New update is available. Click here to update.

Add One to Linked List

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.

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

Approach 1

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

Try Problem

Add One to Linked List

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:

Note:

Input Format:

Output Format:

Note:

Constraints:

Approach 1

Algorithm:

Description of Reverse function:

Interested in Coding Ninjas Flagship Courses?