Переместить все нечетные числа после четных чисел в реализации односвязного списка C++

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

Например.

Given Linked List : 1, 2, 3, 4, 5, 6, 7
After Modification : 2, 4, 6, 1, 3, 5, 7

Из приведенного выше рис. мы можем видеть, как будет работать функция.

Пока заголовок списка нечетный, он копируется во вспомогательный узел, а элемент, следующий за заголовком, становится новым заголовком. Вспомогательный узел добавляется после обновления хвоста и хвоста. Точно так же все узлы с нечетными значениями удаляются со своих позиций и добавляются после хвоста списка.

Вот функции advance, getLastNode, isOdd и exchangeEvenOdd.

static void advance(Node*& node)
{
    assert (node != nullptr);
    node = node->next;
}

С помощью этой функции узел переходит к следующему узлу.

Node* getLastNode()
{
    Node *node = head;
    while (node->next != nullptr)
            node = node->next;

    return node;
}

Эта функция возвращает последний узел связанного списка.

bool isOdd(int num)
{
    if (num % 2 != 0)
        return true;
    else
        return false;
}

Эта функция проверяет, является ли введенное значение четным или нечетным.

void exchangeEvenOdd()
{
    Node *node = nullptr;
    Node *lastNodeToTest = getLastNode();
    Node *tail = lastNodeToTest;

    while (isOdd(head->data) == true)
    {
        node = head;
        advance(head);
        tail->next = node;
        advance(tail);
    }

    Node *tmp = head;
    Node *curr = head;

    while (tmp->next != lastNodeToTest)
    {
        if (isOdd(curr->next->data) == true)
        {
            node = curr->next;
            curr->next = node->next;
            tail->next = node;
            advance(tail);
        }
        else
        {
            //advance "curr" and "tmp" only when next node to it is even
            advance(curr);
            advance(tmp);
        }
    }

    if (isOdd(curr->next->data) == true && tmp->next == lastNodeToTest)
    {
        node = lastNodeToTest;
        curr->next = lastNodeToTest->next;
        tail->next = lastNodeToTest;
        advance(tail);
    }
    tail->next = nullptr;
    lastNodeToTest = nullptr;
    node = nullptr;
}

Реализация С++

#include <iostream>
#include <utility>
#include <cassert>

class LinkedList
{
    struct Node
    {
        int data;
        Node * next = nullptr;
        Node(int value)   : data(std::move(value)), next(nullptr) {}
    };
    Node *head;

  public:
    LinkedList() : head(nullptr) {}
    ~LinkedList()
    {
        Node *tmp = nullptr;
        while (head)
        {
            tmp = head;
            head = head->next;
            delete tmp;
        }
        head = nullptr;
    }

    void insert(int);
    void exchangeEvenOdd();
    void printList() const;

  private:
    static void advance(Node*& node)
    {
        assert (node != nullptr);
        node = node->next;
    }

    Node* getLastNode()
    {
        Node *node = head;
        while (node->next != nullptr)
              node = node->next;

        return node;
    }

    bool isOdd(int num)
    {
        if (num % 2 != 0)
            return true;
        else
            return false;
    }
};

void LinkedList::insert(int value)
{
    Node *node = new Node(std::move(value));
    Node *tmp = head;
    if (tmp == nullptr)
    {
        head = node;
    }
    else
    {
        tmp = getLastNode();
        tmp->next = node;
    }
}

void LinkedList::exchangeEvenOdd()
{
    Node *node = nullptr;
    Node *lastNodeToTest = getLastNode();
    Node *tail = lastNodeToTest;

    while (isOdd(head->data) == true)
    {
        node = head;
        advance(head);
        tail->next = node;
        advance(tail);
    }

    Node *tmp = head;
    Node *curr = head;

    while (tmp->next != lastNodeToTest)
    {
        if (isOdd(curr->next->data) == true)
        {
            node = curr->next;
            curr->next = node->next;
            tail->next = node;
            advance(tail);
        }
        else
        {
            //advance "curr" and "tmp" only when next node to it is even
            advance(curr);
            advance(tmp);
        }
    }

    if (isOdd(curr->next->data) == true && tmp->next == lastNodeToTest)
    {
        node = lastNodeToTest;
        curr->next = lastNodeToTest->next;
        tail->next = lastNodeToTest;
        advance(tail);
    }
    tail->next = nullptr;
    lastNodeToTest = nullptr;
    node = nullptr;
}

void LinkedList::printList() const
{
    if (head == nullptr)
    {
        std::cout << "Empty List \n";
        return;
    }

    Node *node = head;

    while (node != nullptr)
    {
        std::cout << node->data << " ";
        advance(node);
    }

    std::cout << "\n";
}

int main()
{
    LinkedList ll1;
    ll1.insert(1);
    ll1.insert(2);
    ll1.insert(3);
    ll1.insert(4);
    ll1.insert(5);
    ll1.insert(6);
    ll1.insert(7);
    std::cout << "Original List : ";
    ll1.printList();

    ll1.exchangeEvenOdd();
    std::cout << "New List : ";
    ll1.printList();
}

Посмотреть этот код на Github

Ссылка:
Введение в алгоритмы
Руководство по проектированию алгоритмов
Простые структуры данных и алгоритмы

Вам также может понравиться

Объединить два отсортированных связанных списка (на месте)
Разделить одноциклический связанный список
Двойной циклический связанный список
Обратить связанный список
Поиск длины цикла в связном списке
Двухсвязный список
Односвязный список

Следите за мной в Facebook и Twitter

Первоначально опубликовано на https://programmercave0.github.io 8 февраля 2018 г.