[draft article: need to add code discussion]
What is the fastest way of detecting the circular property of a linked list? I have implemented one of the algorithms in C++ just for fun.
In this program, using addItem function you can add more items into the linked list.
Code snippet below includes the solution in an OOP implementation.
#include <iostream> using namespace std; class LL { public: int itemValue; LL *itemNext; }; class CircularLinkedList { public: CircularLinkedList(); ~CircularLinkedList(); void Create(); void fixCircular(); protected: void addItem(int n); LL *head; LL *current; }; // The constructor CircularLinkedList::CircularLinkedList() { head = NULL; current = NULL; } // The destructor CircularLinkedList::~CircularLinkedList() { LL *temp=NULL; current = head; int i = 0; while (current) { temp = current; i = current->itemValue; current = current->itemNext; delete temp; cout<<"deleted element "<<i<itemValue = n; head = current; } // not first time else { current->itemNext = new LL; current = current->itemNext; current->itemValue = n; current->itemNext = NULL; } } void CircularLinkedList::Create() { addItem(1); addItem(2); addItem(3); addItem(4); addItem(5); // create circular linked list // Comment next block if you want to provide a linear linked list // to check whether fixCircular can detect linear linked lists if (current) { current->itemNext = head; cout<<"Circular linked list has been created."<<endl; } } void CircularLinkedList::fixCircular() { LL* fastPointer = head; LL* slowPointer = head; if (head == NULL) { cout<<"Linked list is empty. Please add items."<itemNext; } else break; if (fastPointer == slowPointer) break; if (slowPointer) slowPointer = slowPointer->itemNext; else break; if (fastPointer) { fastPointer = fastPointer->itemNext; } else break; } if (fastPointer == slowPointer) { fastPointer->itemNext = NULL; cout<<"Linked list is Circular! Removed cycle."<<endl; } else cout<<"Not a circular linked list."<<endl; } int main () { CircularLinkedList demoLL; demoLL.Create(); demoLL.fixCircular(); return 0; }
code recovered from web archive, check if update is missed