ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Given a linked list, check if it has a cycle in it, solution in C++

prodevelopertutorial December 23, 2018

Solution Explanation:

Take an extra pointer “fast” and assign its starting point to head.

Every iteration moves the “fast” pointer 2 steps forward and “head” pointer 1 step forward.

At certain point, if there is a cycle, both “head” and “fast” pointer will meet at the same location.

 

Note: By this method, we loose the head pointer. To retain the head pointer, copy the head pointer address to a separate temp variable and restore the head pointer after the calculation has been completed.

 

Solution in C++

#include<iostream>
#include<vector>

using namespace std;

struct Node
{
public:
	int data;
	Node *next;

	Node(int x)
	{
		data = x;
		next = NULL;
	}
};

bool hasCycle(Node *head) 
{
    Node *fast;
    fast = head;
    while (head)
    {
        head = head->next;
        if (fast->next && fast->next->next)
            fast = fast->next->next;
        else
            return false;
            
        if (fast == head)
            return true;
    }
    
    return false;
}

int main()
{

	Node *start = new Node(1);
	start -> next = new Node(2);
	start -> next -> next = new Node(3);
	start -> next -> next -> next = new Node(4);
	start -> next -> next -> next -> next = new Node(5);

	//create a cycle
	start -> next -> next -> next -> next = start;
 	
 	if(hasCycle(start))
 		cout<<"There is a cycle in the list"<<endl;
 	else
 		cout<<"There is NO cycle in the list"<<endl;


	return 0;
}

Output:

There is a cycle in the list

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io