Detect loops in a linked list [closed]

Question

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.

Task:

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.

Answer 1

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;
}

Answer 2

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;
    }
}

Answer 3

Ada

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

linked_lists.ads:

generic
   type Element_Type is private;
package Linked_Lists is

   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;

end Linked_Lists;

linked_lists.adb:

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;

end Linked_Lists;

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;

end Linked_Lists;

Answer 4

Haskell

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 Control.Monad.Instances ()
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

Answer 5

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]);
    }
}