ADD two Linked List
/***
You have two numbers represented by a linked list, where each node contains a
single digit. The digits are stored in reverse order, such that the 1’s digit is
at the head of the list. Write a function that adds the two numbers and returns
the sum as a linked list.
EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8
***/
// the same length?
//trick: new a empty node as head and delete when finished
#include<iostream>
using namespace std;
class Node {
public:
int value;
Node* next;
Node() {
value = 0;
next = nullptr;
}
Node(int v, Node* n) {
value = v;
next = n;
}
};
Node* addList(Node *n1, Node *n2) {
Node *newList, *p;
int carry = 0, sum = 0;
newList = new Node();
p = newList;
while(n1 != nullptr && n2 != nullptr) {
sum = n1->value + n2->value;
if(carry) {
sum += carry;
carry = 0;
}
if(sum >= 10) {
carry = sum / 10;
sum = sum % 10;
}
Node *n = new Node();
n->value = sum;
p->next = n;
p = p->next;
n1 = n1->next;
n2 = n2->next;
}
if(carry) {
Node *n = new Node();
n->value = carry;
p->next = n;
}
p = newList->next;
delete newList;
return p;
}
void main() {
Node n1, n2, n3, n4, n5, n6;
Node *sum;
n1.value = 3;
n1.next = &n2;
n2.value = 1;
n2.next = &n3;
n3.value = 5;
n3.next = nullptr;
n4.value = 5;
n4.next = &n5;
n5.value = 9;
n5.next = &n6;
n6.value = 2;
n6.next = nullptr;
sum = addList(&n1, &n4);
while(sum != nullptr) {
cout<<sum->value<<" -> ";
sum = sum->next;
}
cout<<endl;
}
You have two numbers represented by a linked list, where each node contains a
single digit. The digits are stored in reverse order, such that the 1’s digit is
at the head of the list. Write a function that adds the two numbers and returns
the sum as a linked list.
EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8
***/
// the same length?
//trick: new a empty node as head and delete when finished
#include<iostream>
using namespace std;
class Node {
public:
int value;
Node* next;
Node() {
value = 0;
next = nullptr;
}
Node(int v, Node* n) {
value = v;
next = n;
}
};
Node* addList(Node *n1, Node *n2) {
Node *newList, *p;
int carry = 0, sum = 0;
newList = new Node();
p = newList;
while(n1 != nullptr && n2 != nullptr) {
sum = n1->value + n2->value;
if(carry) {
sum += carry;
carry = 0;
}
if(sum >= 10) {
carry = sum / 10;
sum = sum % 10;
}
Node *n = new Node();
n->value = sum;
p->next = n;
p = p->next;
n1 = n1->next;
n2 = n2->next;
}
if(carry) {
Node *n = new Node();
n->value = carry;
p->next = n;
}
p = newList->next;
delete newList;
return p;
}
void main() {
Node n1, n2, n3, n4, n5, n6;
Node *sum;
n1.value = 3;
n1.next = &n2;
n2.value = 1;
n2.next = &n3;
n3.value = 5;
n3.next = nullptr;
n4.value = 5;
n4.next = &n5;
n5.value = 9;
n5.next = &n6;
n6.value = 2;
n6.next = nullptr;
sum = addList(&n1, &n4);
while(sum != nullptr) {
cout<<sum->value<<" -> ";
sum = sum->next;
}
cout<<endl;
}
Comments
Post a Comment