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.
Source: adding 1 to the linked list
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 *reverse(Node *head)
{
Node * prev = NULL;
Node * current = head;
Node * next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
Node *addUtil(Node *head)
{
Node* res = head;
Node *temp, *prev = NULL;
int sum;
int carry = 1;
while (head != NULL)
{
sum = carry + head->data;
carry = (sum >= 10)? 1 : 0;
sum = sum % 10;
head->data = sum;
temp = head;
head = head->next;
}
if (carry > 0)
temp->next = new Node(carry);
return res;
}
Node* addOne(Node *head)
{
head = reverse(head);
head = addUtil(head);
return reverse(head);
}
void printList(Node *node)
{
while (node != NULL)
{
cout << node->data;
node = node->next;
}
cout<<endl;
}
int main()
{
Node *head = new Node(1);
head->next = new Node(9);
head->next->next = new Node(9);
head->next->next->next = new Node(9);
head->next->next->next->next = new Node(9);
cout << "old list is: ";
printList(head);
head = addOne(head);
cout << "resultant linked list: ";
printList(head);
return 0;
}
Output:
old list is: 19999
resultant linked list: 20000Implementation 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;
}
//for reversing the linked list
static Node reverseList(Node head)
{
Node previousNode = null;
Node currentNode = head;
Node next = null;
while (currentNode != null) {
next = currentNode.next;
currentNode.next = previousNode;
previousNode = currentNode;
currentNode = next;
}
return previousNode;
}
static Node add1One(Node head)
{
Node result = head;
Node temp = null, prev = null;
int carry = 1, sum;
while (head != null)
{
sum = carry + head.data;
carry = (sum >= 10) ? 1 : 0; //carry updation
sum = sum % 10; //if greater than 10
head.data = sum;
temp = head;
head = head.next;
}
if (carry > 0)
temp.next = newNode(carry);
return result;
}
static Node addOne(Node head)
{
head = reverseList(head); //for reversing the linked list
head = add1One(head);
return reverseList(head);
}
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)
{
Node head = newNode(2);
head.next = newNode(1);
head.next.next = newNode(9);
head.next.next.next = newNode(9);
head.next.next.next.next = newNode(9);
head.next.next.next.next.next = newNode(9);
System.out.print("Previous List is: ");
printList(head);
head = addOne(head);
System.out.print("New list is: ");
printList(head);
}
}
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).
568+ registered 
