Изменить последовательность указателей так, чтобы отрицательные числа находились в начале списка

#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
struct Node       //Структура являющаяся звеном списка
{
    int x;     //Значение x будет передаваться в список
    Node *Next, *Prev; //Указатели на адреса следующего и предыдущего элементов списка
};
 
class List   //Создаем тип данных Список
{
    Node *Head, *Tail; //Указатели на адреса начала списка и его конца
 
public:
    List() :Head(nullptr), Tail(nullptr) {}; //Инициализируем адреса как пустые
    ~List(); //Деструктор
    void Show(); //Функция отображения списка на экране
    void Add(int x); //Функция добавления элементов в список
    void Sort();
};
 
List::~List() //Деструктор
{
    while (Head) //Пока по адресу на начало списка что-то есть
    {
        Tail = Head->Next; //Резервная копия адреса следующего звена списка
        delete Head; //Очистка памяти от первого звена
        Head = Tail; //Смена адреса начала на адрес следующего элемента
    }
}
 
void List::Add(int x)
{
    Node *temp = new Node; //Выделение памяти под новый элемент структуры
    temp->Next = nullptr;  //Указываем, что изначально по следующему адресу пусто
    temp->x = x;//Записываем значение в структуру
 
    if (Head != nullptr) //Если список не пуст
    {
        temp->Prev = Tail; //Указываем адрес на предыдущий элемент в соотв. поле
        Tail->Next = temp; //Указываем адрес следующего за хвостом элемента
        Tail = temp; //Меняем адрес хвоста
    }
    else //Если список пустой
    {
        temp->Prev = nullptr; //Предыдущий элемент указывает в пустоту
        Head = Tail = temp; //Голова=Хвост=тот элемент, что сейчас добавили
    }
}
 
void List::Show()
{
    Node *temp=Head; //Временно указываем на адрес первого элемент
    while (temp!= nullptr) 
    {
    cout<<temp->x<<" ";
    temp=temp->Next; 
    }
    
    cout << "\n";
}
 
void List::Sort()
{
 
    struct Node *node, *lastnegative, *prev; 
 
    node = Head; 
    prev = nullptr; 
    lastnegative = nullptr;
 
    do
    {
        if (node->x<0)
        {           
            if (Head == node)
            
                             lastnegative = node;
            
            if (lastnegative == nullptr)
            {
                prev->Next = node->Next;
                node->Next = Head;
                Head = node;            
                lastnegative = node;
                lastnegative->Next = node;
                node = prev;
            }
            else
                if (lastnegative->Next == node)
                {
                    lastnegative = node;
                }
                else
                {
                    prev->Next = node->Next;
                    node->Next = lastnegative->Next;
                    lastnegative->Next = node;
                    lastnegative = node;
                    node = prev;
                }
        }
        else prev = node;
        node = node->Next;
    }
 
    while (node != nullptr);
}
 
int main()
{
    system("CLS");
    List lst; //Объявляем переменную, тип которой есть список
    lst.Add(1); //Добавляем в список элементы
    lst.Add(-2);
    lst.Add(3);
    lst.Add(4);
    lst.Add(5);
 
 
 
    lst.Show(); //Отображаем список на экране
    lst.Sort();
    lst.Show();
    cout << "\n";
 
    system("PAUSE");
}

#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;
}