Извлечение четных чисел из единого связанного списка

Question

Я думал часами, но все еще не могу понять.

Функция должна извлекать в отдельный список все узлы, для которых предикат, примененный к члену, «данных» списка возвращает правда. По сути, он должен возвращать список четных чисел, но переменная 'head', которая передается в качестве аргумента, должна содержать только нечетные числа. Новые функции типа Node не могут быть созданы внутри функции.

template <typename T, typename Pred>
Node<T>* extract(Node<T>*& head, Pred predicate) {
}

Полный код:

#include <iostream>
#include <string>

template<typename T>
struct Node {
    T data;
    Node* next;
};

template <typename T>
void showList(const Node<T>* head) {

    while (head != nullptr) {
        std::cout << head->data << " ";
        head = head->next;
    }
    std::cout << std::endl;

}

template <typename T>
Node<T>* arrayToList(const T arr[], size_t size) {
    Node<T> *head = nullptr;

    for (int i = (int)size - 1; i >= 0; i--) { //size_t works weird here
        Node<T> *n = new Node<T>;
        n->data = arr[i];
        n->next = head;
        head = n;
    }

    return head;
}

template <typename T, typename Pred>
Node<T>* extract(Node<T>*& head, Pred predicate) {



    return nullptr;
}

template <typename T>
void deleteList (Node<T>*& head) {
    while (head != nullptr) {
        Node<T> *tmp = head;
        std::cout << "DEL " << head->data << "; ";
        head = head->next;
        delete tmp;
    }
    std::cout << std::endl;
}

bool isLong(const std::string& s) {
    return s.size() >= 5;
}

int main(int argc, const char * argv[]) {
    using std::string;
    int tabi[] = {2,1,4,3,6,5,7,8};
    size_t sizei = sizeof(tabi)/sizeof(tabi[0]);
    Node<int> *listAi = arrayToList(tabi, sizei);
    showList(listAi);
    Node<int> *listBi = extract(listAi, [](int n) -> bool{
        return n % 2 == 0;
    });
    showList(listAi);
    showList(listBi);
    deleteList(listAi);
    deleteList(listBi);

    string tabs[]{"Kasia", "Ola", "Ala", "Zosia", "Ela", "Basia"};
    size_t sizes = sizeof(tabs)/sizeof(tabs[0]);
    Node<string> *listAs = arrayToList(tabs, sizes);
    showList(listAs);
    Node<string> *listBs = extract(listAs, isLong);
    showList(listAs);
    showList(listBs);
    deleteList(listAs);
    deleteList(listBs);

}

UPD: теперь, похоже, работает:

template <typename T, typename Pred>
Node<T>* extract(Node<T>*& head, Pred predicate) {
        Node<T> *odd = nullptr, *even = nullptr, *current = head;
        Node<T> *oddStart = nullptr, *evenStart = nullptr, *prev = nullptr;

        while (current != nullptr) {
            if (!predicate(current->data) && oddStart == nullptr){
                oddStart = current;
            } else if (predicate(current->data) && evenStart == nullptr) {
                evenStart = current;
            } else {
                break;
            }
            current = current->next;
        }

        current = head;
        even = evenStart;
        odd = oddStart;

        while (current != nullptr) {
            if (predicate(current->data)) {
                prev = current;
                current = current->next;
                even->next = prev;
                even = even->next;
            } else {
                prev = current;
                current = current->next;
                odd->next = prev;
                odd = odd->next;
            }
        }

        even->next = nullptr;
        odd->next = nullptr;
        head = oddStart;

        return evenStart;
    }