Last Updated: Mar 27, 2024

## Introduction

Here in this blog, we are asked to see various approaches to add 1 to a number represented as a linked list. We are already familiar that a linked list is a data structure that contains two fields: one address field and one data field. Now we have to think of the logic that what can we do to add a number 1 to it at any position.

Recommended Topic, Floyds Algorithm

### Problem statement

In this problem, we are assigned a number represented as a linked list, and we must add 1 to it and display the result as a linked list. The problem statement is straightforward; we are given a number in the form of a linked list. This means we'll get the head of the linked list, and we'll have to add 1 to the number represented by the linked list.

Let us understand the problem statement with the help of an example.

### Sample Example

Assume we've been given the number 39999. As a result, the linked list will be as follows:

3 â†’ 9 â†’ 9 â†’ 9 â†’ 9

As our argument, we will get the head pointing to the first node of the linked list, which is 1.

As a result, the head node will point to the first node:

head â†’3 â†’ 9 â†’ 9 â†’ 9 â†’ 9

After adding one, our linked list will look like this: head â†’4 â†’ 0 â†’ 0 â†’ 0 â†’ 0

What is the outcome of adding 1 to 39999 = 40000?

The problem statement is quite clear with the above example.

In the above diagram, we can see that the number given is 1->9->9->9. And we have to add 1 to this number according to the problem statement. So adding it we get the result: 2->0->0->0.

## Approach 1: Brute Force Approach

This approach is very simple to implement and straightforward. In this approach,  we perform an arithmetic operation beginning with the one's place digit and progressing to the tenth place digit, hundredth place digit, and so on, we must obtain the one's place digit in order to add one to it. The last digit of our number in the form of a linked list is now the one's place digit. However, we cannot move backward in the Singly Linked List because only the next pointer is provided. As a result, we can reverse the linked list and perform operations beginning with the first node of the reversed linked list.

Let us see its algorithm.

### Steps of algorithm

Step 1: Reverse the given linked list. Begin the linked list traversal and take two variables sum and carry.

Step 2: The variable sum will store the value at a specific location (node), and carry will carry forward with the carry from the preceding sum given by (sum/10).

Step 3: Because we are adding one, the total can be either equal to or less than ten. As a result, carry will be one for sums greater than ten and zero for sums less than ten.

Step 4: Continue down the list, storing the appropriate value in the resultant list node given by sum %  10.

Step 5: Finally, reverse the linked list for the correct output.

Let us see a diagram to understand this algorithm.

Let us see the implementation of this approach in the next section of this blog.

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node* next;
Node(int value){
data=value;
next=NULL;
}
};

{
Node * prev = NULL;
Node * next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
{
Node *temp, *prev = NULL;
int sum;
int carry = 1;
{
carry = (sum >= 10)? 1 : 0;
sum = sum % 10;
}
if (carry > 0)
temp->next = new Node(carry);
return res;
}
{
}
void printList(Node *node)
{
while (node != NULL)
{
cout << node->data;
node = node->next;
}
cout<<endl;
}
int main()
{
cout << "old list is: ";
cout << "resultant linked list: ";
return 0;
}
``````

Output:

``````old list is: 19999

### Implementation in Java

``````public class Linked_List {
static class Node {
int data;
Node next;
}

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

{
Node previousNode = null;
Node next = null;
while (currentNode != null) {
next = currentNode.next;
currentNode.next = previousNode;
previousNode = currentNode;
currentNode = next;
}
return previousNode;
}

{
Node temp = null, prev = null;

int carry = 1, sum;

{

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

sum = sum % 10; //if greater than 10

}

if (carry > 0)
temp.next = newNode(carry);

return result;
}

{
}

static void printList(Node node)
{
while (node != null) {
System.out.print(node.data);
node = node.next;
}
System.out.println();
}

public static void main(String[] args)
{

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

System.out.print("New list is: ");
}
}
``````

Output:

``````Previous List is: 219999
New list is: 220000``````

Let us analyze the time and complexity of this approach.

#### Complexity analysis

Time complexity

This approach will take O(n), As we make three passes, two for reversing the list and one for adding, where N is the total number of nodes in the linked list.

Space complexity

This will not cost any memory space. And it will take O(1).

## Approach 2: Recursive Solution

In this approach, we will follow the recursive approach. Reach the last node recursively then forward. The recursive solution does not necessitate the reversal of the linked list.

### Steps of algorithm

Step 1: Go back to the last node and add 1 to it.

Step 2: Now, while traversing from the last node to the first node, keep track of the carry and update the node values accordingly.

Step 3:  If the value of carry is 1 at the end of the traversal, create a new head node with that value.

Step 4: At the end of this phase, if the pointer variable points to a node, the length is odd; otherwise, the length is even.

Let us understand this approach with the help of an example.

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};

//this function is for the creation of the linked list
Node* newNode(int data)
{
Node* new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}

// Recursively add 1 from end to beginning and returns
// carry after all nodes are processed.
{
return 1;

// Add carry returned be next node call

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

{

// If there is carry after traversing all node then add new node to the linked list
if (carry) {
Node* newNode = new Node;
newNode->data = carry;
return newNode;
}

}

void printList(Node* node) //printing linked list
{
while (node != NULL) {
cout<<node->data;
node = node->next;
}
cout<<endl;
}

int main(void)
{

return 0;
}``````

Output:

``````linked list is: 299999

Now let us analyze the time and complexity of the above approach.

#### Complexity analysis

Time complexity

The time complexity of this algorithm is O(N).

Space complexity

The space complexity is O(N) as we are using here recursive stack.

#### What is a singly linked list?

The singly linked list contains nodes with a data field and a next field. The next field points to the next node. In other words, singly-linked lists have nodes that contain a reference to the next node in the list.

We will set the next pointer of the tail node to the head pointer to convert a singly linked list to a circular linked list.

1. Make a copy of the head pointer, let's say it duplicate.
2. With the help of a loop, traverse the linked list until you reach the tail node (the last node).
3. Now move the tail node's next pointer to the head node. duplicate->next=head.

#### Why do insertion and deletion have an O(1) complexity in the linked list?

When inserting a node in the middle of a linked list, the assumption is that you are already at the address where the node must be inserted. Indexing is treated as a distinct operation. Insertion is thus O(1), but getting to the middle node is O(n). As long as you know a reference, adding to a linked list doesn't really necessitate a traversal.

## Conclusion

To conclude this blog, firstly we discussed the problem statement and different ways to solve the problems. For the first approach, we discussed its algorithm, pseudo-code, and complexities. And then we discussed another approach. We eventually saw how both the ways are different from each other.

Recommended Problems -

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Topics covered
1.
Introduction
1.1.
Problem statement
1.2.
Sample Example
2.
Approach 1: Brute Force Approach
2.1.
Steps of algorithm
2.2.
Implementation in C++
2.3.
Implementation in Java
2.3.1.
Complexity analysis
3.
Approach 2: Recursive Solution
3.1.
Steps of algorithm
3.2.
Implementation in C++
3.2.1.
Complexity analysis
4.