Ошибка выполнения при сортировке односвязного списка

Question

Я написал реализацию связанного списка (который предназначен для типа данных int). Кажется, работает нормально за исключением , когда я пытаюсь отсортировать список таким образом, что все нечетные элементы должны идти после всех четных элементов с сохранением исходного порядка четных и нечетных чисел.

После отладки в MS Visual Studio я обнаружил, что в функции oddevenSort() for l oop, кажется, работает бесконечно ... как будто каким-то образом tail->next не обновлялся до nullptr. Я не могу, кажется, gr asp, где ошибка лежит в моей логике c.

#include<iostream>

template<class T>
class SLL_Node
{
public:
    T info;
    SLL_Node* next;
    SLL_Node();
    SLL_Node(T el, SLL_Node<T>* n = nullptr);

};

template<class T>
class SLL
{
private:
    SLL_Node<T>* head, * tail;
    size_t size;
public:
    SLL();
    ~SLL();
    bool isEmpty() const;
    size_t get_size() const;
    void add_to_head(T el);
    void add_to_tail(T el);
    void delete_at(size_t); //delete at a certain index. Index starting from 1. Throws an error //message if index out of bounds or list empty. 

    void display()const; //the logic is for mostly primitive data types and not user defined data //types (including classes)
    void oddevenSort();
};

template<class T>
bool SLL<T>::isEmpty() const
{
    if (tail == nullptr)
        return true;
    else
        return false;
}

template<class T>
SLL_Node<T>::SLL_Node() : next{ nullptr }
{}

template<class T>
SLL_Node<T>::SLL_Node(T el, SLL_Node<T>* n) : info{ el }, next{ n }
{}

template<class T>
SLL<T>::SLL()
{
    size = 0;
    head = tail = nullptr;
}

template<class T>
void SLL<T>::add_to_tail(T el)
{
    ++size;
    if (!isEmpty())
    {
        tail->next = new SLL_Node<T>(el);
        tail = tail->next;
    }
    else
        head = tail = new SLL_Node<T>(el);
}

template<class T>
void SLL<T>::add_to_head(T el)
{
    head = new SLL_Node<T>(el, head);
    if (tail == nullptr) //if empty
    {
        tail = head;
    }
    ++size;
}

template<class T>
void SLL<T>::display()const
{
    std::cout << '\n';
    for (SLL_Node<T>* tmp{ head }; tmp != nullptr; tmp = tmp->next)
    {
        std::cout << tmp->info << "->";
    }
    std::cout << "NULL\n";
}

template<class T>
void SLL<T>::delete_at(size_t index)
{


    if (index >= 1 && index <= size) //bound checking 
    {
        if (!isEmpty()) //we dont need is empty since size takes care of that but still adding it for clarity
        {

            if (head == tail && index == 1) //if list only has one node and we delete head node
            {
                delete head;
                head = tail = nullptr;
            }

            //otherwise if list more than one node

            else if (index == 1) //if deleting head node
            {
                SLL_Node<T>* tmp{ head };
                head = head->next;
                delete tmp;
                tmp = nullptr;
            }

            else //deleting other nodes
            {
                SLL_Node<T>* tmp{ head->next }, * pred{ head };
                for (size_t i{ 2 }; i < index; ++i)
                {
                    tmp = tmp->next;
                    pred = pred->next;
                }
                pred->next = tmp->next;
                if (tmp == tail)
                {
                    tail = pred;
                }
                delete tmp;
                tmp = nullptr;
            }

        }
    }

    else
    {
        std::cout<<"\nError! Either the list is empty or the index entered is out of bounds!\n";
    }
}

template<class T>
void SLL<T>::oddevenSort()
{
    SLL_Node<T>* t=head;
    size_t count{1};
    for (; t != nullptr; t = t->next)
    {
        if (((t->info) % 2) != 0)
        {
        add_to_tail(t->info);
        delete_at(count);

        }
        ++count;
    }
}

main :

int main()
{
    SLL<int> a;
    a.add_to_head(1);
    a.add_to_head(2);
    a.add_to_tail(3);
    a.add_to_tail(4);
    a.add_to_head(6);
    a.add_to_tail(7);
    a.add_to_head(5);
    a.display();
    //a.oddevenSort();
    a.display();
    return 0;
}

Answer 1

Рассмотрим пример ввода для oddevenSort a(1)->b(2) ->c(3)->null

1. на 1-й итерации t указывает на a(1) создан новый узел с данными 1, которые добавляются в конце списка типа b(2)->c(3)->d(1)->null.
2. На 2-й итерации t будет указывать на узел b(2), а в списке никаких изменений не будет.
3. На 3-й итерации t будет указывать на узел c(3) новый узел создается с данными 3, которые добавляются в конец списка, например b(2)->d(1)->e(3)->null.
4. на 4-й итерации t будет указывать на d(1), который создает новый узел в конце список. Итерация продолжается и продолжается рекурсивно, не прерывая l oop.

Каждый раз, когда вам не нужно удалять и создавать новый узел. Вы можете разделить четные и нечетные узлы и составить окончательный список.

Вот обновленный фрагмент

template<class T>
void SLL<T>::oddevenSort()
{
    SLL_Node <T>tempOddHeader;
    SLL_Node <T> *tempOddPtr = &tempOddHeader;
    SLL_Node <T> tempEvenHeader;
    SLL_Node <T> *tempEvenPtr = &tempEvenHeader;

    SLL_Node<T>* t = head;
    tempOddHeader.next = nullptr;
    tempEvenHeader.next = nullptr;

    while(t)
    {
        if (((t->info) % 2) != 0) {
            //append to the odd list
            tempOddPtr->next = t;
            tempOddPtr = tempOddPtr->next;
            t = t->next;
            tempOddPtr->next = nullptr;
        }
        else {
            //append to the even list
            tempEvenPtr->next = t;
            tempEvenPtr = tempEvenPtr->next;
            t = t->next;
            tempEvenPtr->next = nullptr;
        }
    }

    tempEvenPtr->next = tempOddHeader.next;
    head = tempEvenHeader.next;
    tail = tempOddPtr;
}