# Detect loops in a linked list [closed]

This comes from one of my favorite interview questions, though apparently it is now a fairly well-known puzzle. I have no way of knowing, but if you have already heard the answer it would be polite to let others try instead.

Write a function that takes as input a singly-linked list and returns true if it loops back on itself, and false if it terminates somewhere.

Here's some example code in C as a starting point so you can see what I mean, but feel free to write your answer in whatever language you like:

struct node
{
void *value;
struct node *next;
};

int has_loops(struct node *first)
{
/* write your own loop detection here */
}


### Hints:

There is a way to make this function run in O(n) time with a constant amount of extra memory. Good on you if you figure it out, but any working answer deserves some upvotes in my book.

• You can make this more general (and applicable to languages which don't have pointers and references) if you rephrase it in terms of a function f:int->int. Given f and x0, let F(x) = if x=0 then 0 else f(x). Is there an int n such that f^n(x0) = 0? Commented Aug 26, 2011 at 7:11
• That should, of course, read F^n(x0) = 0 Commented Aug 26, 2011 at 7:18
• @Peter: Yes, that's about equivalent, although the way you describe f suggests that it is a total function when it isn't. For example, it isn't correct to call f on any value that isn't of the form f^k(x0) for some k. Think about it like a monad if you want to apply it more generally, not as a function whose domain is integers. Commented Aug 26, 2011 at 7:37
• I suppose if you want to instantly segfault, you can treat f as a total function :) Commented Aug 26, 2011 at 9:38
• This could be nicely asked as a logic question to a person: You and your friend are in a maze and suspect you have been traveling in a circle, how can you confirm your suspensions? What if you have no items and are completely naked. The second would be analogous to having no memory in a system. The first could be solved using bread crumbs or what not, however you could tell the person the loop may be 100km, do you have enough bread? Commented Aug 26, 2011 at 15:37

## C, non-golfed

The idea is to have to pointers p1 and p2 that traverse the list. p2 moves twice as fast as p1. If p2 reaches p1 at some point then there is a loop. Here is the C code (not tested, though).

struct node
{
void *value;
struct node *next;
};

int has_loops(struct node *p)
{
struct node *p1 = p, *p2 = p->next;
if (!p2) return 0;

while (p1 != p2) {
// p1 goes one step
p1 = p1->next;
if (!p1) return 0;

// p2 goes two steps
p2 = p2->next;
if (!p2) return 0;
p2 = p2->next;
if (!p2) return 0;
}

return 1;
}

• The line if (!p1) return 0 could be replaced by assert p1 if you really want to check for bugs in your compiler. Commented Aug 26, 2011 at 9:50
• PT: Sure. I will leave it like this for symmetry. Could also make a #define ADVANCE(p) if (!(p = p->next)) return 0 Commented Aug 26, 2011 at 10:30

Since the solution is already in the open, I think it's fair to step in now with Brent's algorithm, which is the one I'm familiar with from integer factorisation.

#define bool int
#define false 0
#define true 1

bool has_loops(struct node *first) {
if (!first) return false;

struct node *a = first, *b = first;
int step = 1;

while (true) {
for (int i = 0; i < step; i++) {
b = b->next;
if (!b) return false;
if (a == b) return true;
}

a = a->next;
if ((step << 1) > 0) step <<= 1;
}
}


The "Floyd's Cycle-Finding Algorithm" is the best solution. It's also called "The Tortoise and the Hare Algorithm".

generic
type Element_Type is private;

type Node is private;
type List is private;

function Has_Loops (L : List) return Boolean;

private

type List is access Node;
type Node is record
Value   : Element_Type;
Next    : List;
end record;



package body Linked_Lists is

function Has_Loops (L : List) return Boolean is
Slow_Iterator : List := L;
Fast_Iterator : List := null;
begin
-- if list has a second element, set fast iterator start point
if L.Next /= null then
Fast_Iterator := L.Next;
end if;

while Fast_Iterator /= null loop

-- move slow iterator one step
-- guaranteed to be /= null, since it is behind fast iterator
Slow_Iterator := Slow_Iterator.Next;

-- move fast iterator one step
-- guaranteed to be valid, since while catches null
Fast_Iterator := Fast_Iterator.Next;
-- move fast iterator another step
-- null check necessary
if Fast_Iterator /= null then
Fast_Iterator := Fast_Iterator.Next;
end if;

-- if fast iterator arrived at slow iterator -> loop detected
if Fast_Iterator = Slow_Iterator then
return True;
end if;

end loop;

-- fast iterator arrived end, no loop present.
return False;
end Has_Loops;



here is the implementation of the Brent algorithm:

package body Linked_Lists is

function Has_Loops (L : List) return Boolean is
Turtle : List     := L;
Rabbit : List     := L;
Steps  : Natural  := 0;
Limit  : Positive := 2;
begin

-- is rabbit at end?
while Rabbit /= null loop

-- increment rabbit
Rabbit := Rabbit.Next;
-- increment step counter
Steps := Steps + 1;

-- did rabbit meet turtle?
if Turtle = Rabbit then
-- LOOP!
return True;
end if;

-- is it time to move turtle?
if Steps = Limit then
Steps := 0;
Limit := Limit * 2;
-- teleport the turtle
Turtle := Rabbit;
end if;

end loop;

-- rabbit has reached the end
return False;
end Has_Loops;


• It's provably not the best solution, actually. Commented Aug 26, 2011 at 9:49
• What do you mean, Peter? Commented Aug 26, 2011 at 10:15
• well, it is O(n) time and O(1) space, seems optimal for me Commented Aug 26, 2011 at 10:22
• Apparently, Brent's cycle detection algorithm is faster. Commented Aug 26, 2011 at 10:34
• @Clueless, Gareth's comment is precisely what I meant. It's like A* vs Dijkstra: asymptotically they're the same but you can prove that A* will never do more work than Dijkstra and that it will sometimes do less. Commented Aug 26, 2011 at 10:39

Naive algorithm:

import Data.Set (Set)
import qualified Data.Set as Set

type Id = Integer
data Node a = Node { getValue :: a, getId :: Id }

hasLoop :: [Node a] -> Bool
hasLoop = hasLoop' Set.empty

hasLoop' :: Set Id => [Node a] -> Bool
hasLoop' set xs = case ns of
[] -> False
x:xs' -> let
ident = getId x
set' = Set.insert ident set
in if Set.member ident set
then True
else hasLoop' set' xs'


Floyd's Cycle-Finding Algorithm:

import Control.Monad (join)
import Data.Function (on)
import Data.Maybe (listToMaybe)

type Id = Integer
data Node a = Node { getValue :: a, getId :: Id }

next :: [a] -> Maybe [a]
next [] = Nothing
next (_:xs) = Just xs

nexts :: [a] -> [a] -> (Maybe [a], Maybe [a])
nexts xs ys = (next xs, next $next ys) hasLoop :: [Node a] -> Bool hasLoop = uncurry hasLoops' . join nexts hasLoop' :: Maybe [Node a] -> Maybe [Node a] -> Bool hasLoop' (Just xs) (Just ys) | on (==) (getId . listToMaybe) xs ys = True | otherwise = uncurry hasLoop'$ nexts xs ys
hasLoop' _ Nothing = False
hasLoop' Nothing _ = False -- not needed, but there for case completeness


# D

This is a solution I thought of myself. It runs in O(n) and uses O(1) memory.

What I'm doing is simply iterating through the list and reversing all the pointers. If the list contains a cycle, you'll eventually end up at the beginning of the list and otherwise you end up at the end, which is somewhere else if your list is longer than 1. Now you've determined the result you can restore the list by simply reversing the pointers again.

Here is my code and a test:

import std.stdio;

// The list structure.
struct node(T)
{
T data;
node!T * next;

this(T data) {this.data = data; next = null;}
}

bool hasLoop(T)(node!T * first)
{
// List shorter than two nodes has no loops.
if(!first || !first.next)
{
return false;
}

// Keep iterating through the list, while reversing the pointers.
node!T * previous = null,
current = first;
while(current)
{
auto next = current.next;
current.next = previous;
previous = current;
current = next;
}

// If the last node was the beginning of the list, there was a cycle.
// Otherwise, there are none.
bool result = previous == first;

// Do the reversal again to restore the list to its original state.
current = previous;
previous = null;
while(current)
{
auto next = current.next;
current.next = previous;
previous = current;
current = next;
}

// Done!
return result;
}

// Test
unittest
{
// Build a list.
int[] elems = [1,2,3,4,5,6,7,8,42];

auto list = new node!int(elems[0]);
auto curr = list;
foreach(x; elems[1..\$])
{
curr.next = new node!int(x);
curr = curr.next;
}

// Outcomment the line below to test for a non-cycle list.
curr.next = list.next.next.next;

// Do cycle check.
writeln(hasLoop(list) ? "yes" : "no");

// Confirm the list is still correct.
curr = list;
for(int i = 0; i < elems.length; ++i, curr = curr.next)
{
assert(curr.data == elems[i]);
}
}

• If you iterate through the list once to reverse the pointers, and then once more to put them back the way they were originally, isn't that O(2n)? Commented May 23, 2012 at 22:35
• @Gareth, O-notation ignores constant factors. Commented May 24, 2012 at 6:42