//https://www.geeksforgeeks.org/move-occurrences-element-end-linked-list/
#include <iostream>
using namespace std;
class node {
public:
int data;
node *next;
node () {
data = 0;
next= NULL;
}
node (int x) {
data = x;
next= NULL;
}
};
class LL {
public:
node *head;
LL() {
head = NULL;
}
void insert(int x);
void print();
void move(int x);
};
void LL::insert(int x) {
node *n = new node(x);
if (head == NULL)
head = n;
else {
node *temp=head;
while (temp->next)
temp = temp->next;
temp->next = n;
}
}
void LL::print() {
node *n = head;
while (n!=NULL) {
cout<< n->data << "->";
n = n->next;
}
cout<< "NULL\n";
}
void LL:: move (int x) {
node *current = head;
node *last = head;
node *prev = NULL;
while (last->next!=NULL)
last = last->next;
node *last2 = last;
while (current != last2) {
if (current->data== x && prev == NULL) {
prev = current;
current = current->next;
head = current;
last->next = prev;
last= last->next;
last->next = NULL;
prev=NULL;
}
else if (current->data == x && prev!=NULL) {
prev->next = current->next;
last->next = current;
last= last->next;
last->next = NULL;
current = prev->next;
}
else if (current->data != x) {
prev = current;
current = current->next;
}
}
}
int main() {
LL h;
int x;
while (true) {
cin>> x;
if (x== -9)
break;
else
h.insert(x);
}
cout<< "Enter the element to move: ";
cin>>x;
h.print();
h.move(x);
h.print();
}