Last Updated on November 25, 2022 by Prepbytes
In this article, we will learn how to add one to linked list. As we know inked list points to every next node as well as contains the address of the next node and sometimes adding one to linked list can also increase the length of the linked list. let’s try to understand the logic to add 1 to linked list.
How to add one to the number represented as linked list.
You are given a linked list representing a number such that each individual node acts as a digit of the number.
Example:
The list
HEAD->1->2->3->NULL corresponds to the number 123. You to add 1 to this number to get 124 i.e. 1->2->4.See original problem statement here
EXPLANATION to add one to linked list:
Approach 1 to add 1 to linked list(Reverse the linked list):
Reverse given linked list. For example, 1-> 9-> 9 -> 9 is converted to 9-> 9 -> 9 ->1.For this changed linked list now traverse the list, in the left-most node add one. if this node’s value is equal to 9 then propagate a carry to the next Node. Do the same procedure until the carry is there.
Reverse the string back as in original form and then returned the head to get the string printed.
struct Node
{
int data;
Node* next;
};
Node *newNode(int data)
{
Node *new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
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 *addOneUtil(Node *head)
{
Node* res = head;
Node *temp, *prev = NULL;
int carry = 1, sum;
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 = newNode(carry);
return res;
}
Node* addOne(Node *head)
{
head = reverse(head);
head = addOneUtil(head);
return reverse(head);
}
void printList(Node *node)
{
while (node != NULL)
{
printf("%d", node->data);
node = node->next;
}
printf("\n");
}
int main(void)
{ int t;scanf("%d",&t);
while(t--)
{
char s[100000];
scanf("%s",s);
int x=s[0]-'0';
Node* head1=newNode(x);
Node* head=head1;
for(int i=1;i<strlen(s);i++)
{
head1->next=newNode(s[i]-'0');
head1=head1->next;
}
head = addOne(head);
printList(head); }
return 0;
}
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
Node* next;
};
Node *newNode(int data)
{
Node *new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
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 *addOneUtil(Node *head)
{
Node* res = head;
Node *temp, *prev = NULL;
int carry = 1, sum;
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 = newNode(carry);
return res;
}
Node* addOne(Node *head)
{
head = reverse(head);
head = addOneUtil(head);
return reverse(head);
}
void printList(Node *node)
{
while (node != NULL)
{
cout<<node->data;
node = node->next;
}
printf("\n");
}
int main(void)
{ int t;scanf("%d",&t);
while(t--)
{
string s;
cin>>s;
int x=s[0]-'0';
Node* head1=newNode(x);
Node* head=head1;
for(int i=1;i<s.length();i++)
{
head1->next=newNode(s[i]-'0');
head1=head1->next;
}
head = addOne(head);
printList(head); }
return 0;
}
class prepbytes
{
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;
}
static Node reverse(Node head)
{
Node prev = null;
Node current = head;
Node next = null;
while (current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
static Node addOneUtil(Node head)
{
Node res = head;
Node temp = null, prev = null;
int carry = 1, sum;
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 = newNode(carry);
return res;
}
static Node addOne(Node head)
{
head = reverse(head);
head = addOneUtil(head);
return reverse(head);
}
static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data);
node = node.next;
}
System.out.println();
}
//main
}
# your code goes here
class Node:
# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to reverse the linked list
def reverse(self):
prev = None
current = self.head
while(current is not None):
next = current.next
current.next = prev
prev = current
current = next
self.head = prev
# Function to insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Utility function to print the LinkedList
def printList(self):
temp = self.head
while(temp):
print (temp.data,end=" ")
temp = temp.next
# Driver program to test above functions
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(85)
print ("Given Linked List")
llist.printList()
llist.reverse()
print ("\nReversed Linked List")
llist.printList()
Approach 2 to add 1 to linked list(Recursive):
Recursively reach the last node and forward carry to previous nodes. Recursive solution doesn’t require reversing of linked list.
#include <bits/stdc++.h>
using namespace std;
struct node{
int data;
node* next;
};
node* newnode(int x)
{
node* temp=new node();
temp->data=x;
temp->next=NULL;
return temp;
}
node* reverse(node* head)
{
if(head==NULL||head->next==NULL)
return head;
node* rest=reverse(head->next);
head->next->next=head;
head->next=NULL;
return rest;
}
int main()
{
int t;cin>>t;
while(t--)
{
string s;
cin>>s;
int x=s[0]-'0';
node* head1=newnode(x);
node* head=head1;
for(int i=1;i<s.length();i++)
{
head1->next=newnode(s[i]-'0');
head1=head1->next;
}
node* headnew=reverse(head);
int carry=1,sum=0;node* prev,*head2=headnew;
while(headnew!=NULL)
{
sum=headnew->data+carry;
carry=sum/10;
headnew->data=sum%10;
//cout<<sum%10<<" ";
prev=headnew;
headnew=headnew->next;
}
if(carry)
{
prev->next=newnode(carry);
prev=prev->next;
}
node* headnew2=reverse(head2);
while(headnew2!=NULL)
{
cout<<headnew2->data;
headnew2=headnew2->next;
}
cout<<"\n";}
return 0;
}
class prepbytes {
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;
}
static int addWithCarry(Node head)
{
if (head == null)
return 1;
int res = head.data + addWithCarry(head.next);
head.data = (res) % 10;
return (res) / 10;
}
static Node addOne(Node head)
{
int carry = addWithCarry(head);
if (carry > 0)
{
Node newNode = newNode(carry);
newNode.next = head;
return newNode;
}
return head;
}
static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data);
node = node.next;
}
System.out.println();
}
//main
}
# your code goes here
class Node:
# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
def reverseUtil(self, curr, prev):
# If last node mark it head
if curr.next is None:
self.head = curr
# Update next to prev node
curr.next = prev
return
# Save curr.next node for recursive call
next = curr.next
# And update next
curr.next = prev
self.reverseUtil(next, curr)
# This function mainly calls reverseUtil()
# with previous as None
def reverse(self):
if self.head is None:
return
self.reverseUtil(self.head, None)
# Function to insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Utility function to print the LinkedList
def printList(self):
temp = self.head
while(temp):
print(temp.data,end=" ")
temp = temp.next
# Driver program
llist = LinkedList()
llist.push(8)
llist.push(7)
llist.push(6)
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)
print("Given linked list")
llist.printList()
llist.reverse()
print("\nReverse linked list")
llist.printList()
In this blog, we have explained how to add one to linked list. We have explained two different approaches first one is by reversing the list and another one is recursive and also explained the updation of the carry variable corresponds with the sum variable and code implementation in various languages as well.T brush up your skills in a linked list, you can check out MYCODE | Competitive Programming.
FAQs related to add one to linked list.
1. When we update the carry variable while adding one to the linked list?
When the sum becomes more than 10 then carry is 1 else it is 0.
2. Can a LinkedList store different data types?
Yes, it’s allowed as long as the list is declared as List <Object> or List <Serializable>, which both String and Integer extend/implement
3. Is the linked list homogeneous?
The linked list is a dynamic data structure that stores homogeneous data elements