-
Notifications
You must be signed in to change notification settings - Fork 47
/
Add as linked List numbers
139 lines (115 loc) · 2.8 KB
/
Add as linked List numbers
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
// C++ program to add two numbers
// represented by linked list
#include <bits/stdc++.h>
using namespace std;
/* Linked list node */
class Node {
public:
int data;
Node* next;
};
/* Function to create a
new node with given data */
Node* newNode(int data)
{
Node* new_node = new Node();
new_node->data = data;
new_node->next = NULL;
return new_node;
}
/* Function to insert a node at the
beginning of the Singly Linked List */
void push(Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = newNode(new_data);
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Adds contents of two linked lists and
return the head node of resultant list */
Node* addTwoLists(Node* first, Node* second)
{
// res is head node of the resultant list
Node* res = NULL;
Node *temp, *prev = NULL;
int carry = 0, sum;
// while both lists exist
while (first != NULL
|| second != NULL) {
// Calculate value of next
// digit in resultant list.
// The next digit is sum of
// following things
// (i) Carry
// (ii) Next digit of first
// list (if there is a next digit)
// (ii) Next digit of second
// list (if there is a next digit)
sum = carry + (first ? first->data : 0)
+ (second ? second->data : 0);
// update carry for next calulation
carry = (sum >= 10) ? 1 : 0;
// update sum if it is greater than 10
sum = sum % 10;
// Create a new node with sum as data
temp = newNode(sum);
// if this is the first node then
// set it as head of the resultant list
if (res == NULL)
res = temp;
// If this is not the first
// node then connect it to the rest.
else
prev->next = temp;
// Set prev for next insertion
prev = temp;
// Move first and second
// pointers to next nodes
if (first)
first = first->next;
if (second)
second = second->next;
}
if (carry > 0)
temp->next = newNode(carry);
// return head of the resultant list
return res;
}
// A utility function to print a linked list
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
/* Driver code */
int main(void)
{
Node* res = NULL;
Node* first = NULL;
Node* second = NULL;
// create first list 7->5->9->4->6
push(&first, 6);
push(&first, 4);
push(&first, 9);
push(&first, 5);
push(&first, 7);
printf("First List is ");
printList(first);
// create second list 8->4
push(&second, 4);
push(&second, 8);
cout << "Second List is ";
printList(second);
// Add the two lists and see result
res = addTwoLists(first, second);
cout << "Resultant list is ";
printList(res);
return 0;
}
// This code is contributed by rathbhupendra