#include <iostream>
#include <cstdlib>
struct Node {
int x;
Node* Next, *Prev;
};
class List {
Node* Head, *Tail;
public:
List();
~List();
void Show(void);
void Add(int x);
Node* Partition(bool (pcmp)(int));
void Clear(void);
void Swap(Node* p1, Node* p2);
};
List::List(void):Head(nullptr), Tail(nullptr){}
List::~List(){
this->Clear();
}
void List::Show(void){
for(auto p = Head; p != nullptr; p = p->Next)
std::cout << p->x << ' ';
std::cout << std::endl;
}
void List::Add(int x){
Node* p;
try {
p = new Node();
} catch(...){
return;
}
p->x = x;
p->Next = p->Prev = nullptr;
if(Head == nullptr)
Head = Tail = p;
else {
p->Prev = Tail;
Tail = Tail->Next = p;
}
}
//перестановка
Node* List::Partition(bool (pcmp)(int)){
Node* p = Head;
while((p != nullptr) && pcmp(p->x))
p = p->Next;
for(Node* i = p; i != nullptr; i = i->Next){
if(pcmp(i->x)){
if(i != p){
this->Swap(i, p);
std::swap(i, p);
}
p = p->Next;
}
}
return p;
}
// обмен узлов
void List::Swap(Node* p1, Node* p2) {
if((p1 == nullptr) || (p2 == nullptr))
return;
Node* prev1 = p1->Prev;
Node* prev2 = p2->Prev;
if(prev1 != nullptr)
prev1->Next = p2;
p2->Prev = prev1;
if(prev2 != nullptr)
prev2->Next = p1;
p1->Prev = prev2;
Node* t1 = p1->Next;
Node* t2 = p2->Next;
p1->Next = p2->Next;
if(t2 != nullptr)
t2->Prev = p1;
p2->Next = t1;
if(t1 != nullptr)
t1->Prev = p2;
if(Head == p1)
Head = p2;
else if(Head == p2)
Head = p1;
if(Tail == p1)
Tail = p2;
else if(Tail == p2)
Tail = p1;
}
//удаление всех
void List::Clear(void){
Node* tmp;
while(Head != nullptr){
tmp = Head;
Head = Head->Next;
delete tmp;
}
Tail = nullptr;
}
int main(void){
List lst;
lst.Add(100);
for(int i = 0; i < 10; ++i)
lst.Add(-9 + std::rand() % 19);
lst.Add(-200);
lst.Show();
lst.Partition([] (int x) { return (x < 0); });
lst.Show();
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGxpYj4KCnN0cnVjdCBOb2RlIHsKCWludCB4OwoJTm9kZSogTmV4dCwgKlByZXY7Cn07CgpjbGFzcyBMaXN0IHsKCU5vZGUqIEhlYWQsICpUYWlsOwpwdWJsaWM6CglMaXN0KCk7Cgl+TGlzdCgpOwoJdm9pZCAgU2hvdyh2b2lkKTsKCXZvaWQgIEFkZChpbnQgeCk7CglOb2RlKiBQYXJ0aXRpb24oYm9vbCAocGNtcCkoaW50KSk7Cgl2b2lkICBDbGVhcih2b2lkKTsKCXZvaWQgIFN3YXAoTm9kZSogcDEsIE5vZGUqIHAyKTsKfTsKCkxpc3Q6Okxpc3Qodm9pZCk6SGVhZChudWxscHRyKSwgVGFpbChudWxscHRyKXt9Ckxpc3Q6On5MaXN0KCl7Cgl0aGlzLT5DbGVhcigpOwp9Cgp2b2lkIExpc3Q6OlNob3codm9pZCl7Cglmb3IoYXV0byBwID0gSGVhZDsgcCAhPSBudWxscHRyOyBwID0gcC0+TmV4dCkKCQlzdGQ6OmNvdXQgPDwgcC0+eCA8PCAnICc7CglzdGQ6OmNvdXQgPDwgc3RkOjplbmRsOwp9Cgp2b2lkIExpc3Q6OkFkZChpbnQgeCl7CglOb2RlKiBwOwoJdHJ5IHsKCQlwID0gbmV3IE5vZGUoKTsKCX0gY2F0Y2goLi4uKXsKCQlyZXR1cm47Cgl9CglwLT54ICAgID0geDsKCXAtPk5leHQgPSBwLT5QcmV2ID0gbnVsbHB0cjsKCglpZihIZWFkID09IG51bGxwdHIpCgkJSGVhZCA9IFRhaWwgPSBwOwoJZWxzZSB7CgkJcC0+UHJldiA9IFRhaWw7CgkJVGFpbCAgICA9IFRhaWwtPk5leHQgPSBwOwoJfQp9CgkKLy/Qv9C10YDQtdGB0YLQsNC90L7QstC60LAKTm9kZSogTGlzdDo6UGFydGl0aW9uKGJvb2wgKHBjbXApKGludCkpewoJTm9kZSogcCA9IEhlYWQ7Cgl3aGlsZSgocCAhPSBudWxscHRyKSAmJiBwY21wKHAtPngpKQoJCXAgPSBwLT5OZXh0OwoJCglmb3IoTm9kZSogaSA9IHA7IGkgIT0gbnVsbHB0cjsgaSA9IGktPk5leHQpewoJCWlmKHBjbXAoaS0+eCkpewoJCQlpZihpICE9IHApewoJCQkJdGhpcy0+U3dhcChpLCBwKTsKCQkJCXN0ZDo6c3dhcChpLCBwKTsKCQkJfQoJCQlwID0gcC0+TmV4dDsKCQl9Cgl9CglyZXR1cm4gcDsKfQoKLy8g0L7QsdC80LXQvSDRg9C30LvQvtCyCnZvaWQgTGlzdDo6U3dhcChOb2RlKiBwMSwgTm9kZSogcDIpIHsKCWlmKChwMSA9PSBudWxscHRyKSB8fCAocDIgPT0gbnVsbHB0cikpCgkJcmV0dXJuOwoKCU5vZGUqIHByZXYxID0gcDEtPlByZXY7CglOb2RlKiBwcmV2MiA9IHAyLT5QcmV2OwoKCWlmKHByZXYxICE9IG51bGxwdHIpCgkJcHJldjEtPk5leHQgPSBwMjsKCXAyLT5QcmV2ID0gcHJldjE7CgoJaWYocHJldjIgIT0gbnVsbHB0cikKCQlwcmV2Mi0+TmV4dCA9IHAxOwoJcDEtPlByZXYgPSBwcmV2MjsKCglOb2RlKiB0MSA9IHAxLT5OZXh0OwoJTm9kZSogdDIgPSBwMi0+TmV4dDsKCglwMS0+TmV4dCA9IHAyLT5OZXh0OwoJaWYodDIgIT0gbnVsbHB0cikKCQl0Mi0+UHJldiA9IHAxOwoKCXAyLT5OZXh0ID0gdDE7CglpZih0MSAhPSBudWxscHRyKQoJCXQxLT5QcmV2ID0gcDI7CgoJaWYoSGVhZCA9PSBwMSkKCQlIZWFkID0gcDI7CgllbHNlIGlmKEhlYWQgPT0gcDIpCgkJSGVhZCA9IHAxOwoKCWlmKFRhaWwgPT0gcDEpCgkJVGFpbCA9IHAyOwoJZWxzZSBpZihUYWlsID09IHAyKQoJCVRhaWwgPSBwMTsKfQoKLy/Rg9C00LDQu9C10L3QuNC1INCy0YHQtdGFCnZvaWQgTGlzdDo6Q2xlYXIodm9pZCl7CglOb2RlKiB0bXA7Cgl3aGlsZShIZWFkICE9IG51bGxwdHIpewoJCXRtcCAgPSBIZWFkOwoJCUhlYWQgPSBIZWFkLT5OZXh0OwoJCWRlbGV0ZSB0bXA7Cgl9CglUYWlsID0gbnVsbHB0cjsKfQoKCmludCBtYWluKHZvaWQpewoJTGlzdCBsc3Q7Cglsc3QuQWRkKDEwMCk7Cglmb3IoaW50IGkgPSAwOyBpIDwgMTA7ICsraSkKCQlsc3QuQWRkKC05ICsgc3RkOjpyYW5kKCkgJSAxOSk7CgkJCglsc3QuQWRkKC0yMDApOwoJbHN0LlNob3coKTsKCWxzdC5QYXJ0aXRpb24oW10gKGludCB4KSB7IHJldHVybiAoeCA8IDApOyB9KTsKCWxzdC5TaG93KCk7CglyZXR1cm4gMDsKfQ==