Learn Computer Science programming - C# and C++ Algorithms

 

Cyclic Linked Lists


A cyclical linked list is one where the tail node points to the head node.

Question:
You are given a linked list that is either NULL terminated or cyclic. Write a function that takes a pointer to the head of the list and determines which type it is by returning 1 or zero.

Answers:
  1. Traverse the list and mark the nodes that are visited. When the first is repeated and node->previous is the end node. Thmeans it is cyclical if it does not have a NULL pointer. This requires creating a separate array to keep track of the visited nodes. Not efficient.
  2. Find if there is a node being pointed to by 2 pointers. This will also answer the question. Not efficient.
  3. Compare the current node's NEXT pointer to all of the previous nodes. If any are all equal then it is a cyclical list. Not efficient.
  4. Use two pointers. One fast and one slow. Loop through list. If faster pointer catches up to the slower one, then you have a cyclical list. Efficient.
Code
cycliclinkedlist.zip
File Size: 3539 kb
File Type: zip
Download File


The snippet below contains the functions needed to make a cyclic Linked List. The code in the attachment above has the full solution with all of the implementation.

int DLinkedList::IsCyclic ()
{
DLink *SP, *FP;
SP = FP = pHead;

if (FP->Next->Next)
FP = FP->Next->Next;

while (1)
{
if (!FP || !FP->Next)
return 0;
else if (SP == FP || SP == FP->Next)
return 1;
else
{
SP = SP->Next ;
FP = FP->Next->Next; 
}
}
}




wcout << endl << "Determine if list is cyclic..." << endl; 
wcout << "The double liked list is " << DLL.IsCyclic () << endl; 


DLL.MakeCyclic(); 


wcout << endl << "Determine if list is cyclic..." << endl; 
wcout << "The double liked list is " << DLL.IsCyclic () << endl; 


DLL.MakeNOTCyclic ();