How to find the Length of Loop in Linked List | C++ Implementation


Given a Linked List, we have to find does loop exist in Linked List and if yes, find the length of loop.

Floyd Cycle Finding Algorithm

To find loop in the linked list, we need two node pointers slowPtr and fastPtr which starts from the head. slowPtr increments by one node while fastPtr increments by two nodes. If these pointers point at the same node after starting from head then loop exists. This algorithm is known as Floyd Cycle Finding Algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

If loop exists then this function returns node which is pointed by slowPtr and fastPtr and if node doesn’t exist then it returns nullptr.

To calculate length of loop, fastPtr start from its current node and count number of nodes until slowPtr is equal to fastPtr.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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


C++ Implementation to find Length of Loop in a Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

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

View this code on Github

std::move is used to indicate that an object t may be “moved from”, i.e. allowing the efficient transfer of resources from t to another object. It is defined in header <utility>.

Get this post in pdf - Find Length og Loop in a Linked List

Reference:
Introduction to Algorithms
The Algorithm Design Manual
Data Structures and Algorithms Made Easy

You may also like:

Move all Odd numbers after Even numbers in Singly Linked List
Merge two sorted Linked List (in-place)
Split Singly Circular Linked List
Doubly Circular Linked List
Reverse the Linked List
Doubly Linked List
Singly Linked List