Поиск длины цикла в связанном списке | Реализация С++

Учитывая связанный список, мы должны найти, существует ли цикл в связанном списке, и если да, то найти длину цикла.

Чтобы найти цикл в связанном списке, нам нужны два указателя узлов slowPtr и fastPtr, которые начинаются с головы. slowPtr увеличивается на один узел, а fastPtr увеличивается на два узла. Если эти указатели указывают на один и тот же узел после начала с головы, то цикл существует. Этот алгоритм известен как Алгоритм поиска цикла Флойда.

Node* doesLoopExist()
{
    Node *slowPtr = head;
    Node *fastPtr = head;

    while(slowPtr && fastPtr && fastPtr->next)
    {
        slowPtr = slowPtr->next;
        fastPtr = fastPtr->next->next;

        if(slowPtr == fastPtr)
        {
            return slowPtr;
        }
    }
    return nullptr;
}

Если цикл существует, эта функция возвращает узел, на который указывают slowPtr и fastPtr, а если узел не существует, возвращает nullptr.

Чтобы вычислить длину цикла, fastPtr начните с текущего узла и подсчитывайте количество узлов, пока slowPtr не станет равным fastPtr.

int lengthOfLoop()
{
    int count = 0;
    bool loopExist = false;
    Node *slowPtr = nullptr, *fastPtr = nullptr;

    slowPtr = doesLoopExist();
    fastPtr = slowPtr;
    if(slowPtr != nullptr)
    {
        loopExist = true;
    }
    else
    {
        return 0;
    }
    if(loopExist)
    {
        fastPtr = fastPtr->next;
        count++;
        while(slowPtr != fastPtr)
        {
            fastPtr = fastPtr->next;
            count++;
        }
        return count;
    }
    return 0;
}

Реализация С++ для поиска длины цикла в связанном списке

#include <iostream>
#include <utility>

template <class T>
class LinkedList
{
    struct Node
    {
        T data;
        Node * next;
        Node(T value) : data(std::move(value)), next(nullptr) {}
    };
    Node *head;

  public:
    LinkedList() : head(nullptr) {}
    LinkedList(const LinkedList& ll) = delete; //copy constructor
    LinkedList& operator=(const LinkedList& ll) = delete; //copy assignment
    ~LinkedList();
    void insert(T);
    void createLoop(int);
    int lengthOfLoop();
    Node* doesLoopExist()
    {
        Node *slowPtr = head;
        Node *fastPtr = head;

        while(slowPtr && fastPtr && fastPtr->next)
        {
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;

            if(slowPtr == fastPtr)
            {
                return slowPtr;
            }
        }
        return nullptr;
    }
};

template <class T>
void LinkedList<T>::insert(T data)
{
    Node *node = new Node(std::move(data));
    Node *tmp = head;
    if(tmp == nullptr)
    {
        head = node;
    }
    else
    {
        while(tmp->next != nullptr)
        {
            tmp = tmp->next;
        }
        tmp->next = node;
    }
}

template <class T>
void LinkedList<T>::createLoop(int n)
{
    Node *tmp = head;
    Node *tail = head;
    for(int i = 0; i < n-1; i++)
    {
        tmp = tmp->next;
    }

    while(tail->next != nullptr)
    {
        tail = tail->next;
    }
    tail->next = tmp;
}

template <class T>
int LinkedList<T>::lengthOfLoop()
{
    int count = 0;
    bool loopExist = false;
    Node *slowPtr = nullptr, *fastPtr = nullptr;

    slowPtr = doesLoopExist();
    fastPtr = slowPtr;
    if(slowPtr != nullptr)
    {
        loopExist = true;
    }
    else
    {
        return 0;
    }
    if(loopExist)
    {
        fastPtr = fastPtr->next;
        count++;
        while(slowPtr != fastPtr)
        {
            fastPtr = fastPtr->next;
            count++;
        }
        return count;
    }
    return 0;
}

template <class T>
LinkedList<T>::~LinkedList()
{
    Node *tmp = nullptr;
    while(head)
    {
        tmp = head;
        head = head->next;
        delete tmp;
    }
    head = nullptr;
}

int main()
{
    LinkedList<char> ll1;
    ll1.insert('p');
    ll1.insert('r');
    ll1.insert('o');
    ll1.insert('g');
    ll1.insert('r');
    ll1.insert('a');
    ll1.insert('m');
    ll1.insert('m');
    ll1.insert('e');
    ll1.insert('r');

    int nodeNumber = 5;
    //Node number starts from 1

    ll1.createLoop(nodeNumber);
    bool result = ll1.doesLoopExist();
    if(result == true)
    {
        std::cout <<"Loop exist in the Linked List\n";
    }
    else
    {
        std::cout <<"Loop does not exist in the Linked List\n";
    }

    int len = ll1.lengthOfLoop();
    std::cout << "Length of Loop is " << len <<"\n";

    exit(0);
}

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

std::move используется для обозначения того, что объект t может быть «перемещен», т. е. позволяет эффективно передавать ресурсы от t к другому объекту. Он определен в header<utility>.

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

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

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

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

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