# include < iostream >
# include < fstream >
using namespace std ;
struct Node {
int val;
Node * prev ;
Node * next ;
};
int digit_sum ( int n) {
int sum = 0 ;
while (n > 0 ) {
sum += n % 10 ;
n /= 10 ;
}
return sum ;
}
int digit_control ( int n) {
while (n >= 10 ) {
n = digit_sum (n);
}
return n;
}
void eliminate_numbers_with_no_control_digit ( Node * head ) {
Node * curr = head ;
while ( curr != NULL ) {
int control_digit = digit_control ( curr ->val);
if ( control_digit != 0 && curr ->val % control_digit == 0 ) {
// add control digit after current node
Node * new_node = new Node { control_digit , curr , curr -> next };
if ( curr -> next != NULL ) {
curr -> next -> prev = new_node ;
}
curr -> next = new_node ;
curr = new_node -> next ;
} else {
// eliminate current node
Node * prev = curr -> prev ;
Node * next = curr -> next ;
if ( prev == NULL ) {
head = next ;
} else {
prev -> next = next ;
}
if ( next != NULL ) {
next -> prev = prev ;
}
Node * to_delete = curr ;
curr = next ;
delete to_delete ;
}
}
}
void print_list ( Node * head ) {
Node * curr = head ;
while ( curr != NULL ) {
cout << curr ->val << " " ;
curr = curr -> next ;
}
cout << endl ;
}
int main () {
ifstream fin ( "input.txt" ) ;
// create the linked list
Node * head = NULL ;
Node * tail = NULL ;
int num;
while (fin >> num) {
Node * new_node = new Node {num, tail , NULL };
if ( tail == NULL ) {
head = new_node ;
} else {
tail -> next = new_node ;
}
tail = new_node ;
}
fin. close ();
cout << "Original list : " ;
print_list ( head );
eliminate_numbers_with_no_control_digit ( head );
cout << " Modified list : " ;
print_list ( head );
// free memory
Node * curr = head ;
while ( curr != NULL ) {
Node * next = curr -> next ;
delete curr ;
curr = next ;
}
return 0 ;
}