Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 10 Dec, 2019

Cycle Detection in a Singly Linked List

Moderate
Asked in companies
Goldman SachsInformaticaMicrosoft

Problem statement

You are given a Singly Linked List of integers. Return true if it has a cycle, else return false.


A cycle occurs when a node's next points back to a previous node in the list.


Example:
In the given linked list, there is a cycle, hence we return true.

Sample Example 1

Input format :
The first line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence -1 would never be a list element.


The second line contains the integer position 'pos', representing the position (0-indexed) in the linked list where the tail connects. If 'pos' is -1, there is no cycle in the linked list.


Output format :
The only output line contains 'true' if the linked list has a cycle or 'false' otherwise.


Note :
You don't have to print by yourself explicitly. It has been taken care of.

Approaches

01 Approach

We are going to have two loops outer-loop and inner-loop 

  1. Maintain a count of the number of nodes visited in outer-loop.
  2. For every node of the outer-loop, start the inner loop from head.
  3. If the inner-loop visits the node next to the outer-loop node, then return true, else repeat the process for the next iteration of outer-loop.
  4. If outer-loop reaches the end of list or null, then return false.