You’re given the pointer to the head node of a linked list. Find
whether the list contains any cycle (or loop). A linked list is said to
contain cycle if any node is re-visited while traversing the list. The head pointer given may be null meaning that the list is empty.
Input Format
You have to complete the
Output Format
Check whether the linked list has a cycle and
Sample Input
1. First list has no cycle, hence return 0
2. Second list is shown to have a cycle, hence return 1.
Note
After first solving the problem by yourself, see Floyd's cycle-finding algorithm for an efficient solution which uses O(N) time and O(1) additional memory.
------------------------------------------------------------------------------------------------------------
/*
Detect loop in a linked list
List could be empty also
Node is defined as
struct Node
{
int data;
struct Node *next;
}
*/
int HasCycle(Node* head)
{
// Complete this function
// Do not write the main method
Node* fast = head, *slow = head;
while(fast!= NULL){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
return 1;
}
}return 0;
}
----------------------------------------------------------------------------------------------------------
Input Format
You have to complete the
int HasCycle(Node* head)
method
which takes one argument - the head of the linked list. You should NOT
read any input from stdin/console. Number of nodes in a linked list
doesn't exceed 100.Output Format
Check whether the linked list has a cycle and
return 1
if there is a cycle. Otherwise, return 0
. Do NOT print anything to stdout/console.Sample Input
1 --> NULL
1 --> 2 --> 3
^ |
| |
-----
Sample Output0
1
Explanation 1. First list has no cycle, hence return 0
2. Second list is shown to have a cycle, hence return 1.
Note
After first solving the problem by yourself, see Floyd's cycle-finding algorithm for an efficient solution which uses O(N) time and O(1) additional memory.
------------------------------------------------------------------------------------------------------------
/*
Detect loop in a linked list
List could be empty also
Node is defined as
struct Node
{
int data;
struct Node *next;
}
*/
int HasCycle(Node* head)
{
// Complete this function
// Do not write the main method
Node* fast = head, *slow = head;
while(fast!= NULL){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
return 1;
}
}return 0;
}
----------------------------------------------------------------------------------------------------------