Cycle Detection Algorithm: the Hare and the Tortoise
Author
Frank the Bunny
Last Updated
před 9 lety
License
Creative Commons CC BY 4.0
Abstract
Explain how the Floyd's cycle detection algorithm works.
\documentclass[11pt]{article}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{lmodern}
\usepackage{fullpage}
% for algorithm description
\usepackage{alltt}
% for algorithm description in a box
\usepackage{boxedminipage}
% for colorful comment
\usepackage{color}
\setlength{\parskip}{.2em}
\begin{document}
\title{Cycle Detection Algorithm: the Hare and the Tortoise}
\author{Frank the Giant Bunny}
\date{August 27, 2014}
\maketitle
\thispagestyle{empty}
\paragraph{Question}
Using only two pointers,
decide whether a singly-linked list $L$ contains
a loop or not.
\paragraph{Answer}
The simplest answer is to maintain two pointers:
the \texttt{hare} moving \emph{two} steps at a time and
the \texttt{tortoise} moving \emph{one} step at a time.
\noindent\begin{boxedminipage}{\textwidth}
\begin{alltt}
Hare-and-Tortoise(\(L\))
\textcolor{red}{// Input: a linked list \(L\)}
\textcolor{red}{// Output: `yes' if \(L\) contains a loop and `no' otherwise.}
Two pointers \emph{hare} and \emph{tortoise} are initially located at the head of \(L\).
Repeat
If the \emph{hare} reaches the end of \(L\) within two steps, return `no'.
Else
Move the \emph{hare} two steps forward and the \emph{tortoise} one step forward.
If two pointers are located on the same node, return `yes'.
EndIf
EndRepeat
\end{alltt}
\end{boxedminipage}
\paragraph{Why it works}
If the list $L$ doesn't contain a loop,
the hare will reach the end of $L$ sooner than the tortoise
does and the algorithm will eventually return `no'.
If the list $L$ contains a loop, it results in a $\rho$
shape when diagrammed.
\begin{itemize}
\item Once the hare and tortoise enter the
cycle part of the $\rho$ shape,
they are trapped in the loop and
keep rotating around the cyclic path.
\item And the hare enters the cyclic part
sooner than the tortoise does.
\item Assume that the hare and tortoise are separated in $d$
steps when the tortoise enters the cycle.
\item As the tortoise moves only one step while the hare
moves two steps, their distance in the cyclic path keeps decreasing by one for each iteration of the \texttt{Repeat} block of the algorithm.
Hence, two pointers will eventually collide
and the algorithm returns `yes'.
\end{itemize}
\paragraph{Ask yourself}
What if the hare moves \emph{three} steps forward at a time while
the tortoise moves \emph{one} step at a time?
What about other steps? Does the algorithm still work?
\end{document}