-
Notifications
You must be signed in to change notification settings - Fork 10
/
add_2_linked_list.cpp
78 lines (76 loc) · 1.46 KB
/
add_2_linked_list.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
Node* reverseList( Node *head)
{
Node* head1;
Node* prev=NULL;
Node* curr=head;
Node* nxt=NULL;
while(curr!=NULL)
{
nxt=curr->next;
curr->next=prev;
prev=curr;
curr=nxt;
}
head1=prev;
return head1;
}
int length(Node* head)
{
int c=0;
while(head!=NULL)
{
head=head->next;
c++;
}
return c;
}
struct Node* addTwoLists(struct Node* first, struct Node* second)
{
Node* small;
Node* large;
int len1=length(first);
int len2=length(second);
if(len1>len2)
{
small=second;
large=first;
}
else{
small=first;
large=second;
}
Node* f1=reverseList(small);
Node* f2=reverseList(large);
int carry=0;
int sum;
Node* start=NULL;
Node* end=NULL;
while(f1!=NULL || f2!=NULL)
{
int a=f1!=NULL?f1->data:0;
int b=f2!=NULL?f2->data:0;
sum=carry+(a+b);
carry=sum>=10?1:0;
sum=sum%10;
if(start==NULL)
{
start=new Node(sum);
end=start;
}
else
{
end->next=new Node(sum);
end=end->next;
}
if(f1!=NULL)
f1=f1->next;
if(start!=NULL)
f2=f2->next;
}
if(carry>0)
end->next=new Node(carry);
start=reverseList(start);
return start;
}
// Time - O(n)+O(m)
// Space - O(n)+O(m)