You're given a positive integer represented in the form of a singly linked-list of digits. The length of the number is 'n'.
Add 1 to the number, i.e., increment the given number by one.
The digits are stored such that the most significant digit is at the head of the linked list and the least significant digit is at the tail of the linked list.
Input: Initial Linked List: 1 -> 5 -> 2
Output: Modified Linked List: 1 -> 5 -> 3
Explanation: Initially the number is 152. After incrementing it by 1, the number becomes 153.
The first line contains an integer 'n', the length of the number / the length of the linked list.
The second line contains 'n' space separated integers denoting the digits of the number / the nodes of the linked list.
Print space - separated integers denoting the nodes of the output linked list.
You do not need to print anything. You're given the head of the linked list, return the head of the modified list.
3
1 5 2
1 5 3
Initially the number is 152. After incrementing it by 1, the number becomes 153.
2
9 9
1 0 0
Initially the number is 9. After incrementing it by 1, the number becomes 100. Please note that there were 2 nodes in the initial linked list, but there are three nodes in the sum linked list.
The expected time complexity is O('n').
1 <= 'n' <= 10^5
0 <= Node in linked list <= 9
There are no leading zeroes in the number.
Time Limit: 1 sec
Try to reach the last node of the linked list using recursion.
In this approach, we will use recursion to add 1 to the linked list. We can recursively reach the last node, add 1 to it and forward the carry to the previous node.
This solution does not require reversing the linked list.
The steps are as follows:
Node *addOne(Node *‘head’)
O(n), Where 'n' is the length of the number we're given in the form of a linked list.
We are traversing the entire list exactly once, making the time complexity asymptotic to the length of the linked list.
Hence the time complexity is O(n).
O(n), Where 'n' is the length of the number we're given in the form of a linked list.
We are solving the problem recursively, and there will be recursive states equal to the number of nodes.
Hence the space complexity is O(n).
All tags
Sort by
Interview problems
JAVA Code : TC = O(N) SC = O(N)
public static int solve(Node temp){
if(temp == null) return 1;
int carry = solve(temp.next);
temp.data = temp.data+carry;
if(temp.data < 10) return 0;
else temp.data = 0;
return 1;
}
public static Node addOne(Node head) {
int carry = solve(head);
if(carry != 0){
Node newNode = new Node(1);
newNode.next = head;
head = newNode;
}
return head;
}
Interview problems
JavaScript || Recursive & Iterative solution
Recursive solution
function addOne(head) {
if (head === null)
{
return head;
}
let carry = 1;
function rec(node) {
if (node.next === null)
{
node.data += carry;
carry = 0;
if (node.data === 10)
{
node.data = 0;
carry = 1;
}
return;
}
rec(node.next);
node.data += carry;
carry = 0;
if (node.data === 10)
{
node.data = 0;
carry = 1;
}
}
rec(head);
return carry === 1 ? new Node(1, head) : head;
}
Iterative solution (Reversing LL twice
function reverse(head) {
let temp = head, prev = null;
while (temp != null)
{
let node = temp.next;
temp.next = prev;
prev = temp;
temp = node;
}
return prev;
}
function addOne(head) {
if (head === null)
{
return head;
}
let newHead = reverse(head)
let carry = 1, temp = newHead;
while (temp != null)
{
if (temp.data === 9 && carry === 1)
{
temp.data = 0;
carry = 1;
}
else
{
temp.data += carry;
carry = 0;
break;
}
if (temp.next === null && carry === 1)
{
temp.next = new Node(1);
break;
}
temp = temp.next;
}
return reverse(newHead)
}Interview problems
easy cpp || using Recursion
int add1(Node* head){
if(head==NULL){
return 1;
}
int carry = add1(head->next);
head->data=(head->data + carry);
if(head->data < 10){
return 0;
}else{
head->data=(head->data)%10;
return 1;
}
}
Node *addOne(Node *head)
{
int carry=add1(head);
if(carry==1){
Node* New_head= new Node(1);
New_head->next=head;
return New_head;
}else return head;
}
Interview problems
Add one to the LinkedList
public class Solution {
public static Node reverse(Node head){
if(head == null||head.next == null){
return head;
}
Node newnode = reverse(head.next);
Node front = head.next ;
front.next = head ;
head.next = null;
return newnode ;
}
public static Node addOne(Node head) {
head = reverse(head);
Node temp = head ;
if(temp.data+1 <= 9){
head.data+=1;
return reverse(head);
}
int sum = head.data+1;
head.data = (sum)%10;
int carry = (sum)/10;
temp = temp.next;
while(temp!=null){
sum = carry+temp.data ;
temp.data=sum%10;
carry = sum/10;
temp = temp.next;
}
if(carry!=0)
{
Node newnode = new Node(carry);
head = reverse(head);
newnode.next = head ;
head = newnode;
return head ;
}
return reverse(head);
}
}
Interview problems
java solution
public class Solution {
public static Node reverse(Node head){
if(head==null || head.next==null){
return head;
}
Node newNode=reverse(head.next);
Node front=head.next;
front.next=head;
head.next=null;
return newNode;
}
public static Node addOne(Node head) {
// Write your code here.
int carry=1;
head=reverse(head);
Node temp=head;
while(temp!=null){
temp.data=temp.data+carry;
if(temp.data<10){
carry=0;
break;
}else{
temp.data=0;
carry=1;
}
temp=temp.next;
}
if(carry==1){
Node newNode=new Node(1);
head=reverse(head);
newNode.next=head;
return newNode;
}
head=reverse(head);
return head;
}
}
Interview problems
Simplest Cpp Code|O(n)
Node* reversell(Node *head)
{
if(head==NULL||head->next==NULL) return head;
Node *newhead=reversell(head->next);
Node *front=head->next;
front->next=head;
head->next=NULL;
return newhead;
}
Node *addOne(Node *head)
{
// Write Your Code Here.
if(head==NULL) return head;
head=reversell(head);
Node *curr=head;
int carry=1;
while(curr)
{
int sum=curr->data+carry;
if(sum==10)
{
carry=1;
curr->data=0;
curr=curr->next;
}
else {
curr->data=sum;
head=reversell(head);
return head;
}
}
if(carry==1)
{
Node *newnode=new Node(1);
newnode->next=head;
head=newnode;
return head;
}
return NULL;
}
Interview problems
Simple Solution using Stack.
#include <bits/stdc++.h>
Node *addOne(Node *head)
{
// Write Your Code Here.
stack<pair<Node *, int>>st;
int sum = 0;
Node *list = head;
while(list!=nullptr)
{
st.push({list, list->data});
list = list->next;
}
int carry = 1;
while(st.empty()==false)
{
auto p = st.top();
st.pop();
sum = p.second + carry;
p.first->data = sum%10;
carry = sum/10;
}
if(carry)
{
Node *temp = new Node(carry);
temp->next = head;
head = temp;
}
return head;
}
Interview problems
Java Solution | Easy approach
public class Solution {
public static Node reverse(Node head){
if(head == null || head.next == null){
return head;
}
Node prev = null;
Node curr = head;
while(curr != null){
Node nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
return prev;
}
public static Node addOne(Node head) {
// Write your code here.
head = reverse(head);
Node temp = head;
int carry = 1;
while(temp != null){
temp.data = temp.data + carry;
if(temp.data < 10){
carry = 0;
break;
}
else{
temp.data = 0;
carry = 1;
}
temp = temp.next;
}
if(carry == 1){
Node newnode = new Node(1);
head = reverse(head);
newnode.next = head;
return newnode;
}
head = reverse(head);
return head;
}
}
Interview problems
Java Solution
public class Solution {
public static Node reverse(Node head){
Node curr = head;
Node prev = null;
Node n = null;
while(curr != null){
n = curr.next;
curr.next = prev;
prev = curr;
curr = n;
}
return prev;
}
public static Node addOne(Node head) {
// Write your code here.
Node temp = reverse(head);
int carry = 1;
Node t = temp;
Node prev = null;
while(t != null){
int sum = carry;
sum += t.data;
t.data = sum%10;
carry = sum/10;
prev = t;
t = t.next;
}
if(carry != 0){
Node ans = new Node(carry);
prev.next = ans;
}
return reverse(temp);
}
}Interview problems
ADD 1 number
public class Solution {
public static Node addOne(Node head) {
Node dummy = new Node(0);
Node ln = dummy;
ln.next = head;
Node current = head;
while(current!=null)
{
if(current.data!=9)
{
ln = current;
}
current = current.next;
}
ln.data+=1;
current = ln.next;
while(current!=null)
{
current.data = 0;
current = current.next;
}
if(dummy.data == 1)
{
return dummy;
}
return head;
}
}
