Problem of the day
You are given a non-negative integer represented as a linked list of digits (‘N’ is the number of nodes in the linked list). The digits are stored so that the head of the linked list stores the most significant digit.
Your task is to add one to the integer (which is shown in the form of a linked list) and return the head of the linked list after adding 1.
Example:Input: ‘N’ = 3, ‘head’ = [2, 3, 4]
Output: [2, 3, 5]
Explanation: Given number is 234. After adding 1 to it, it becomes 235.
First-line contains 'T', denoting the number of Test cases.
For each Test case:
The first line contains one integer, ‘N’, denoting the number of nodes in the Linked List.
The following line contains ‘N’ integers, denoting the non-negative integer (or the values of nodes of the linked list).
Output format:
Return the head of the linked list after adding 1 to the non-negative integer.
Note:-
You don't need to print anything. Just implement the given function.
1 <= T <= 10
1 <= N <= 100
0 <= Node.value <= 9
The number in the linked list doesn’t contain any leading zeroes except the number 0, where there’s only one node with the value 0.
Time Limit: 1-sec
2
3
2 3 4
4
1 1 1 9
2 3 5
1 1 2 0
Input: ‘N’ = 3, ‘head’ = [2, 3, 4]
Output: [2, 3, 5]
Explanation: Given number is 234. After adding 1 to it, it becomes 235.
For test case 2:
Input: ‘N’ = 4, ‘head’ = [1, 1, 1, 9]
Output: [1, 1, 2, 0]
Explanation: Given number is 1119. After adding 1 to it, it becomes 1120.
2
4
1 9 9 9
4
9 9 9 9
2 0 0 0
1 0 0 0 0
Use a dummy node to consider the case when, after adding 1, the number of digits of our number increases.
We will use a dummy node whose initial value equals 0 and point to our linked list's head. We will use two more temporary nodes, specifically, ‘i’ and ‘j’, initially assigned to the dummy node.
First, we try to find the farthest node from the head of the linked list using node ‘j’, which is not equal to ‘9’. We assign it to ‘i’.
This is because, then, we can say that, after adding 1 to our given integer, the value of all the nodes after the node ‘i’ to the last node of the linked list becomes equal to ‘0’, but the value of the node ‘i’ increase by 1, and don’t become 0 as it’s initial value is not 9. This way, we don’t have to think about the nodes before node ‘i’.
After doing this, we can return the ‘dummy’ node or the node next to the ‘dummy’ node if the value of the dummy node is 0 (which means there is no need for an extra digit in the linked list).
The steps are as follows:-
// Function to add one to the integer represented by Linked List
function addOneToLinkedList(int n, ListNode* head):
O( N ), Where 'N' is the number of nodes in the linked list.
We are iterating over all the nodes of the linked list at most 2 times in the worst-case scenario,
Hence the time complexity is O( N ).
O( 1 ).
We are using only two extra nodes for traversing over the linked list,
Hence the space complexity is O( 1 ).