### striver_79's blog

By striver_79, history, 6 years ago,

Given 2 Linked Lists containing single digit as data representing number with most significant digit at head and least significant at the tail return the addition of both.

The solution must not reverse the given linked lists and do it in O(n) time complexity and constant space complexity(Recursive solution will take O(n) space because of stack).

For example:

9 -> 3 -> 2 -> 2 ->

+

3 -> 4 -> 8 -> 3 ->

=

1 -> 2 -> 8 -> 0 -> 5 .

Can anyone help me out ?

• +11

| Write comment?
 » 6 years ago, # | ← Rev. 2 →   0 it is easily possible in doubly linked list, but question is unclear whether it is singly LL or doubly LL.If singly LL, then you can do this: Pad the shorter list with zeros to make equal length. Start from head and and the digits and insert result to answer linked list at head. (Ex: 5->10->7->12) Now you will have to propagate carry to end. Reverse the answer linked list. Answer linked list can be made from any of two given linked list if you cannot modify the lists then I don't think it is possible in O(1) space as answer will take Ω(n).
•  » » 6 years ago, # ^ |   0 Need to do this in singly LL.
 » 6 years ago, # | ← Rev. 2 →   0 I think I solved this with only four pointers (even without integer variables).First, we do some preparation to cope with the difference of the input lengths. Without loss of generality assume that the first list is longer. To do so, simultaneously advance two pointers from each head. When the second pointer reaches the end, the third pointer will be set to the head of the first list. Then advance the first and third pointers simultaneously until the first pointer reaches the end. At this time, the third pointer is saved. When we iterate the second list from its head, the pointer will be freeze until the pointer on the first list reaches the saved third pointer. While the second pointer is freezing, it reads 0 as the digit. In this way, we can synchronize the two pointers on each list.We use forth and fifth pointers to save the previous node of the beginning of the last 9-run for each list. 9-run means a possibly empty consecutive sequence of 9's on the result of the digit sums (This may not match the final result). When the result of the sum of the current digits is greater or equals to 10 (it carries), the last 9-run is "consumed". The result will be output during the consumption.The second pointer can replace the fifth pointer while the third pointer is being used. Thus the four pointers are enough.
•  » » 6 years ago, # ^ |   0 I understood the part where the third pointer will be after the first pointer reaches the end. Can you please explain me 9 9 9 9 3 2 2 + 3 4 8 3. It will be really helpful if you can explain your approach by this example. Thankyou in advance.
»
6 weeks ago, # |
-15

# include<bits/stdc++.h>

using namespace std;

struct node{

int data;

struct node *link;

};

void add_at_end(struct node *);

struct node * add(struct node *,struct node *);

void print(struct node *);

int main(){

int nodes;

cin>>nodes;

struct node *head=(struct node *)malloc(sizeof(struct node));

cin>>head->data;

head->link=NULL;

for(int j=2;j<=nodes;j++){

add_at_end(head);

}

struct node *head1=(struct node *)malloc(sizeof(struct node));

cin>>head1->data;

head1->link=NULL;

for(int j=2;j<=nodes;j++){

add_at_end(head1);

}

head=add(head,head1);

print(head);

}

void add_at_end(struct node *head){

struct node *temp=(struct node *)malloc(sizeof(struct node

cin>>temp->data;

temp->link=NULL;

while(head!=NULL){

if(head->link==NULL){

head->link=temp;

break;

}

head=head->link;

}

} void print(struct node *head){

while(head!=NULL){

cout<<head->data<<" ";

head=head->link;

}

}

struct node * add(struct node *head,struct node *head1){

struct node *temp=head,*temp1=head;

while(head!=NULL){

if((head->data+head1->data>=10)&&(head==temp1)){

struct node *t=(struct node *)malloc(sizeof(struct node));

t->data=1;

t->link=head;

head->data=((head->data)+(head1->data))%10;

temp1=t;

}
else if((head->data)+(head1->data)>=10){

head->data=((head->data)+(head1->data))%10;

temp->data++;

temp=head;

}

else{

head->data=(head->data+head1->data);

temp=head;

}

head=head->link;

head1=head1->link;

}

return temp1;

}

Output:

4

9 3 2 2

3 4 8 3

1 2 8 0 5