Linked List Cycle Given a linked list with potentially a loop, determine whether the linked list from the first
node contains a cycle in it. For bonus points, do this with constant space.
Parameters
nodes: The first node of a linked list with potentially a loop.
Result
Whether there is a loop contained in the linked list.
Examples
Example 1
Input:
Output:
true
Example 2
Input:
Output:
false
Constraints
Try it yourself
Solution If a linked list has no loop, then when we iterate through the list, we will eventually
reach the end of the list, at which point we can simply return. However, the challenge
is figuring out how to terminate the program if it finds a loop. Otherwise the program
would go on forever.
A simple solution would be to use a set to store the information. We store all the
nodes we have been through and check if we have been there each time we move. However,
a set is not constant memory, and there might be issues with hashing and whatnot. Clearly
there is a better way.
Introducing Floyd's Cycle Finding Algorithm, also known as the Tortoise and Hare Algorithm.
The idea is to have two pointers, the fast pointer (or "hare") moves at double speed of
the slow pointer (or "tortoise"). Each cycle, the tortoise moves once and the hare moves
twice. The idea is that since the cycle must have integer size, when the tortoise and the
hare are both in the cycle, their distance difference must also be an integer. Then,
each cycle, because of their speed difference, the distance between them constantly reduces
until they meet, in which case we know there is a cycle. However, if there is no cycle,
they will never meet because the speed of the hare is always faster.
Time Complexity: O(n)
Technically O(n/2) but again we factor out the constant and we are left with linear time.
Worst case we have, O(2n) as the small pointer moves around the entire array once.
Either way we have O(n) time complexity.
This is a graphics that explains the idea:
Below is an implementation.
Python Java C# JavaScript C++ class Node :
def __init__ ( self, val, next = None ):
self.val = val
self. next = next
def node_next ( node ):
return node. next or node
def has_cycle ( nodes: Node ) -> bool :
tortoise = node_next(nodes)
hare = node_next(node_next(nodes))
while tortoise != hare and hare. next is not None :
tortoise = node_next(tortoise)
hare = node_next(node_next(hare))
return hare. next is not None
if __name__ == '__main__' :
raw_input = [ int (x) for x in input ().split()]
nodes_list = []
for i, entry in enumerate (raw_input):
nodes_list.append(Node(i))
for i, entry in enumerate (raw_input):
if entry != - 1 :
nodes_list[i]. next = nodes_list[entry]
nodes = nodes_list[ 0 ]
res = has_cycle(nodes)
print ( 'true' if res else 'false' )
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
class Solution {
public static class Node < T > {
public T val;
public Node<T> next;
public Node (T val) {
this (val, null );
}
public Node (T val, Node<T> next) {
this .val = val;
this .next = next;
}
}
public static Node<Integer> nextNode (Node<Integer> node) {
if (node.next == null ) {
return node;
}
return node.next;
}
public static boolean hasCycle (Node<Integer> nodes) {
Node<Integer> tortoise = nextNode(nodes);
Node<Integer> hare = nextNode(nextNode(nodes));
while (tortoise != hare && hare.next != null ) {
tortoise = nextNode(tortoise);
hare = nextNode(nextNode(hare));
}
return hare.next != null ;
}
public static List<String> splitWords (String s) {
return s.isEmpty() ? List.of() : Arrays.asList(s.split( " " ));
}
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
List<Integer> rawInput = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
ArrayList<Node<Integer>> nodesList = new ArrayList<>();
for ( int i = 0 ; i < rawInput.size(); i++) {
nodesList.add( new Node<Integer>(i));
}
for ( int i = 0 ; i < rawInput.size(); i++) {
if (rawInput.get(i) != - 1 ) {
nodesList.get(i).next = nodesList.get(rawInput.get(i));
}
}
Node<Integer> nodes = nodesList.get( 0 );
scanner.close();
boolean res = hasCycle(nodes);
System.out.println(res);
}
}
using System;
using System.Collections.Generic;
using System.Linq;
class Solution
{
public class Node < T >
{
public T val;
public Node<T> next;
public Node ( T val )
{
this .val = val;
}
public Node ( T val, Node<T> next )
{
this .val = val;
this .next = next;
}
}
public static Node< int > NextNode ( Node< int > node ) {
if (node.next == null ) {
return node;
}
return node.next;
}
public static bool HasCycle ( Node< int > nodes ) {
Node< int > tortoise = NextNode(nodes);
Node< int > hare = NextNode(NextNode(nodes));
while (tortoise != hare && hare.next != null ) {
tortoise = NextNode(tortoise);
hare = NextNode(NextNode(hare));
}
return hare.next != null ;
}
public static List< string > SplitWords ( string s )
{
return string .IsNullOrEmpty(s) ? new List< string >() : s.Trim().Split( ' ' ).ToList();
}
public static void Main ( )
{
List< int > rawInput = SplitWords(Console.ReadLine()).Select( int .Parse).ToList();
List<Node< int >> nodesList = new List<Node< int >>();
for ( int i = 0 ; i < rawInput.Count; i++)
{
nodesList.Add( new Node< int >(i));
}
for ( int i = 0 ; i < rawInput.Count; i++)
{
if (rawInput[i] != -1 )
{
nodesList[i].next = nodesList[rawInput[i]];
}
}
Node< int > nodes = nodesList[ 0 ];
bool res = HasCycle(nodes);
Console.WriteLine(res ? "true" : "false" );
}
}
class Node {
constructor ( val, next = null ) {
this .val = val;
this .next = next;
}
}
function nextNode ( node ) {
if (node.next == null ) return node;
return node.next;
}
function hasCycle ( nodes ) {
let tortoise = nextNode(nodes);
let hare = nextNode(nextNode(nodes));
while (tortoise !== hare && hare.next != null ) {
tortoise = nextNode(tortoise);
hare = nextNode(nextNode(hare));
}
return hare.next != null ;
}
function splitWords ( s ) {
return s == "" ? [] : s.split( ' ' );
}
function * main ( ) {
const raw_input = splitWords( yield ).map( ( v ) => parseInt (v));
const nodes_list = [];
for ( let i = 0 ; i < raw_input.length; i++) {
nodes_list.push( new Node(i));
}
for ( let i = 0 ; i < raw_input.length; i++) {
if (raw_input[i] != - 1 ) {
nodes_list[i].next = nodes_list[raw_input[i]];
}
}
const nodes = nodes_list[ 0 ];
const res = hasCycle(nodes);
console .log(res);
}
class EOFError extends Error {}
{
const gen = main();
const next = ( line ) => gen.next(line).done && process.exit();
let buf = '' ;
next();
process.stdin.setEncoding( 'utf8' );
process.stdin.on( 'data' , ( data ) => {
const lines = (buf + data).split( '\n' );
buf = lines.pop();
lines.forEach(next);
});
process.stdin.on( 'end' , () => {
buf && next(buf);
gen.throw( new EOFError());
});
}
# include <algorithm> // copy
# include <iostream> // boolalpha, cin, cout
# include <iterator> // back_inserter, istream_iterator
# include <sstream> // istringstream
# include <string> // getline, string
# include <vector> // vector
template < typename T>
struct Node {
T val;
Node<T>* next;
explicit Node (T val, Node<T>* next = nullptr )
: val{ val}, next{next} {}
~ Node () {
delete next;
}
};
Node< int >* next_node (Node< int >* node) {
if (node->next == NULL ) {
return node;
}
return node->next;
}
bool has_cycle (Node< int >* nodes) {
Node< int >* tortoise = next_node (nodes);
Node< int >* hare = next_node ( next_node (nodes));
while (tortoise != hare && hare->next != NULL ) {
tortoise = next_node (tortoise);
hare = next_node ( next_node (hare));
}
return hare->next != NULL ;
}
template < typename T>
std::vector<T> get_words () {
std::string line;
std:: getline (std::cin, line);
std::istringstream ss{line};
std::vector<T> v;
std:: copy (std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std:: back_inserter (v));
return v;
}
int main () {
std::vector< int > rawInput = get_words< int >();
std::vector<Node< int >*> nodeList;
for ( int i = 0 ; i < rawInput. size (); i++) {
nodeList. push_back ( new Node< int >(i));
}
for ( int i = 0 ; i < rawInput. size (); i++) {
if (rawInput[i] != -1 ) {
nodeList[i]->next = nodeList[rawInput[i]];
}
}
Node< int >* nodes = nodeList[ 0 ];
bool res = has_cycle (nodes);
std::cout << std::boolalpha << res << '\n' ;
}
