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;

}

Comments

Popular posts from this blog

Sudoku

Longest prefix matching - trie

Climbing Stairs