  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on November 8, 2022 by Prepbytes ### Introduction

In the article, we will learn to add 1 to a number represented as linked list.As we know a linked list is a linear data structure. In a linked list, the elements are linked using pointers and each node points to the next node. Let’s try to understand how we can 1 to a number represented as linked list.

### Problem Statement

In this problem, we are given a number represented in the form of a linked list, we are required to add 1 to it and report the answer as a linked list.

For Example: Given is a Number 19999 in the form of a linked list, and after adding 1 to linked list, it should give the result as follows:  The problem statement is quite straightforward, we are provided with a number represented in the form of a linked list which means we will be getting the head/root of the linked list as our argument, and we have to add 1 to the number represented as linked list.

Let’s learn programming languages online and try to understand to add 1 to linked list more clearly using an example.

Let’s assume we are given the number 19999. So the linked list will be :

• Initial Linked List: 1 → 9 → 9 → 9 → 9
• We will be getting the head pointing to the 1st node of the linked list, which is 1 as our argument.
• So the head pointer will point to the first node:
head →1 → 9 → 9 → 9 → 9
head →2 → 0 → 0 → 0 → 0
• Which is the result after adding 1 to 19999 = 20000 At this point in time, we have understood how to add 1 to a number represented as linked list. Now try to formulate an approach to add 1 to a number represented as linked list.

• Since we do an arithmetic operation starting from the one’s place digit and then move towards the tenth place digit, hundredth place digit and so on, therefore we need to get hold of the one’s place digit to add 1 to linked list.
• Now the one’s place digit is the last digit of our number given in the form of a linked list. But we cannot move backside in the linked list, as only the next pointer is given.
• So we can reverse the linked list and do operations starting from the first node of the reversed linked list.
• So, our original linked list will be reversed and thus we can now simply add 1 to the head of the linked list (maintaining carry). Finally, we will reverse the list again and will output it as our final linked list.

• Reverse the given Linked List. For example, the given linked list is 1 → 9 → 9 → 9 → 9, after reversing it will become 9 → 9 → 9 → 9 → 1.
• Start the linked list traversal, take 2 variable sum and carry.
• The variable sum will hold the value at a particular place (node) and carry will take forward the carry from the previous sum given by (sum/10).
• Now, since we need to add 1 to linked list, the sum can be either equal than 10 or less than 10.
• Therefore, carry will be 1 for a sum greater than 10 and 0 for a sum less than 10.
• Keep moving forward in the list and store the appropriate value in the resultant list node given by sum%10.
• At last, again reverse the linked list to get the output in the correct format.  ```#include<stdio.h>
#include<stdlib.h>

struct Node
{
int data;
struct Node* next;
struct Node* prev;
};

/* Function to create a new node with given data */
struct Node *newNode(int data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = NULL;
return new_node;
}

/* Function to reverse the linked list */
{
struct Node * prev   = NULL;
struct Node * current = head;
struct Node * next;
while (current != NULL)
{
next  = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}

node of resultant list */
{
// res is head node of the resultant list
struct Node *temp;
struct Node* prev = NULL;

int carry = 1, sum;

while (head != NULL) //while both lists exist
{
// Calculate value of next digit in resultant list.
// The next digit is sum of following things
// (i) Carry
// (ii) Next digit of head list (if there is a
//     next digit)

// update carry for next calculation
carry = (sum >= 10)? 1 : 0;

// update sum if it is greater than 10
sum = sum % 10;

// Create a new node with sum as data

// Move head and second pointers to next nodes
}

// if some carry is still there, add a new node to
// result list.
if (carry > 0)
temp->next = newNode(carry);

// return head of the resultant list
return res;
}

// This function mainly uses addOneUtil().
{

// Add one from left to right of reversed
// list

// Reverse the modified list
}

// A utility function to print a linked list
void printList(struct Node *node)
{
while (node != NULL)
{
printf("%d", node->data);
node = node->next;
}
printf("\n");
}

/* Driver program to test above function */
int main(void)
{

printf("List is ");

printf("\nResultant list is ");

return 0;
}
```
```#include<bits stdc++.h="">
using namespace std;
class Node
{
public:
int data;
Node *next;

Node(int val) {
data = val;
next = NULL;
}
};
{
Node* res = head_ref; // res will point to the head of the resultant list.

int carry = 1 , sum;//Why carry is taken as 1 ? => because we need to add 1

Node* prev; // prev pointer is necessary for the last node, if at last carry is there, we need to add a new Node with value carry.
// (Take example of 9->9->9->9)

carry = (sum >= 10) ? 1 : 0;

}
if (carry > 0) {
prev->next = new Node(carry);
}

return res;
}
Node* prev = NULL, *next;

while (curr != nullptr) {
next = curr->next;
curr->next = prev;

prev = curr;
curr = next;
}

return prev;
}
{

}

void printList(Node *node)
{
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
int main()
{

return 0;
}
```
```class CarryOne {

static class Node
{
int data;
Node next;
}

/* Function to create a new node with given data */
static Node newNode(int data)
{
Node new_node = new Node();
new_node.data = data;
new_node.next = null;
return new_node;
}
{
return 1;

// Add carry returned be next node call

// Update data and return new carry
return (res) / 10;
}

// This function mainly uses addWithCarry().
{

// If there is carry after processing all nodes,
// then we need to add a new node to linked list
if (carry > 0)
{
Node newNode = newNode(carry);
return newNode; // New node becomes head now
}

}

// A utility function to print a linked list
static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data);
node = node.next;
}
System.out.println();
}

/* Driver code */
public static void main(String[] args)
{

System.out.print("List is ");

System.out.println();
System.out.print("Resultant list is ");
}
}
```
```class Node:
def __init__(self, data):
self.data = data
self.next = None

def newNode(data):
return Node(data)

return
curNode.next = None

while(nextNode):
curNode = nextNode
nextNode = nextNode.next
curNode.next = prevNode
prevNode = curNode

return curNode

carry = 0
prev = None

if carry > 0:
prev.next = Node(carry)
return reverseList(k)

return

if __name__ == '__main__':

```

#### Output

2 → 0 → 0 → 0 → 0

Time Complexity: O(n), Overall we are doing a total of 3 passes, 2 for reversing and 1 while adding, where n is the number of nodes in the given LinkedList.
Space complexity: O(1), constant space complexity, as no extra space is used.

#### Can we Do Any Better ?

• Now we have seen that for the above approach to work to add 1 to a number represented as linked list, we need to reverse the list twice. So we are doing two extra traversals worth O(N) complexity.
• However, if we observe carefully, we will see that it is the digit 9 which makes all the changes, for all other digits we just need to increment by 1. But in the case of 9 carry comes into the picture and modifies the whole list.
• So, we can try targeting the digit 9 itself. We don’t need to reverse the linked list.

We will find the last node which is not 9. Now for this, there can be 3 scenarios to add q to linked list:

• Case1: If there exists no node which is not 9, it means every node is 9. For example 9->9->9->9. In such a case we will make every node value equal to 0 and add a new node with value 1 at the front of the list.
• Case2: If the last node of the list is not 9, then simply increment the value of the last node by 1.
• Case3: If the node which is not 9 is somewhere in the middle, and after that, every node is 9. For example 1299, then in such cases increment the last non-nine node by 1 and make all nodes right to it as zero. So 1299 becomes 1300.

We will take 2 pointers, one for storing the last node which is not 9, other for traversing the list. Then handle each case independently.  ```#include<stdio.h>
#include<stdlib.h>

struct Node {
int data;
struct Node* next;
};

/* Function to create a new node with given data */
struct Node* newNode(int data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));;
new_node->data = data;
new_node->next = NULL;
return new_node;
}

{
// If linked list is empty, then
// return carry
return 1;

// Add carry returned be next node call

// Update data and return new carry
return (res) / 10;
}
{

// If there is carry after processing all nodes,
// then we need to add a new node to linked list
if (carry) {
struct Node* newNode  = (struct Node*)malloc(sizeof(struct Node));
newNode->data = carry;
return newNode; // New node becomes head now
}

}
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d", node->data);
node = node->next;
}
printf("\n");
}

/* Driver code */
int main(void)
{

printf("List is ");

printf("\nResultant list is ");

return 0;
}
```
```#include<bits stdc++.h="">
using namespace std;
class Node
{
public:
int data;
Node *next;

Node(int val) {
data = val;
next = NULL;
}
};
void printList(Node *node)
{
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
{
Node* last = NULL , *current_node = head;

//Through this loop we will find the last non-nine node.
while (current_node->next != NULL)
{
if (current_node->data != 9) {
last = current_node;
}
current_node = current_node->next;
}

//This loop will run till the second last node, so for the last node we will check using if condition.
//If the last node itself is not 9. Then simply increment the value by 1 and return the head.
if (current_node->data != 9) {
current_node->data++;
}

//After loop if last is still NULL, that means there is no value which is not 9.
//For example 9->9->9->9
if (last == NULL) {
//1 extra node will be needed.
last = new Node(1);

//then make every node 0
last = last->next;
while (last != NULL) {
last->data = 0;
last = last->next;
}
}

//Last case => when the non-nine node is somewhere in middle;
// we will increment the value and make everything right to it as 0
last->data++;
last = last->next;
while (last != NULL) {
last->data = 0;
last = last->next;
}
}
int main()
{

return 0;
}
```
```class CarryOne{

static class Node
{
int data;
Node next;
}
static Node newNode(int data)
{
Node new_node = new Node();
new_node.data = data;
new_node.next = null;
return new_node;
}

{

Node last = null ;
//Through this loop we will find the last non-nine node.
while (current_node.next != null)
{
if (current_node.data != 9) {
last = current_node;
}
current_node = current_node.next;
}
//This loop will run till the second last node, so for the last node we will check using if condition.
//If the last node itself is not 9. Then simply increment the value by 1 and return the head.
if (current_node.data != 9) {
current_node.data=current_node.data+1;
}
//After loop if last is still NULL, that means there is no value which is not 9.
//For example 9->9->9->9
if (last == null) {
//1 extra node will be needed.
last = newNode(1);
//then make every node 0
last = last.next;
while (last != null) {
last.data = 0;
last = last.next;
}
}
//Last case => when the non-nine node is somewhere in middle;
// we will increment the value and make everything right to it as 0
last.data=last.data+1;
last = last.next;
while (last != null) {
last.data = 0;
last = last.next;
}

}

// A utility function to print a linked list
static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data);
node = node.next;
}
System.out.println();
}

// Driver code
public static void main(String[] args)
{

System.out.print("List is ");

System.out.println();
System.out.print("Resultant list is ");
}
}
```
```class Node:
def __init__(self, data):
self.data = data
self.next = None

def newNode(data):
return Node(data)

return

last = None

# Through this loop we will find the last non-nine node
while current_node.next:

if current_node.data != 9:
last = current_node

current_node = current_node.next

# This loop will run till the second last node, so for the last node we will check using if condition.
# If the last node itself is not 9. Then simply increment the value by 1 and return the head.
if current_node.data != 9:
current_data.data += 1

# After loop if last is still NULL, that means there is no value which is not 9
# For example 9->9->9->9
if last == None:
# 1 extra node will be needed.
last = newNode(1)

# then make every node 0
last = last.next
while last != None:
last.data = 0
last = last.next

# Last case => when the non-nine node is somewhere in middle;
# we will increment the value and make everything right to it as 0
last.data += 1
last = last.next
while last:
last.data = 0
last = last.next

if __name__ == '__main__':

```

#### Output

2 → 0 → 0 → 0 → 0

Time Complexity: O(n) only single pass, where n is the number of nodes in the given LinkedList.
[forminator_quiz id=”4441″]

Footer

1. What is the time complexity to count the number of elements in a linked list?

2. To count the number of elements, you have to traverse through a linked list and it will take O(n) time.

3. What are the basic operations that can be performed in a linked list?

4. We can do traversal, insertion, deletion, searching, updating, sorting and merging in the linked list.

5. Which operation is not supported by the linked list?

6. Circulate is not supported by a linked list as a linked list is a linear collection of data elements whose order is not given by their physical placement in memory.