Home/

...

/

Introduction

Introduction

Some learning resources for fast and slow pointers.

Fast and slow pointers can be used to detect cycles in a linked list. Since the pointers move at different speeds, if a cycle exists, the two are bound to meet. In this case, fast moves ahead by a factor of 2, and slow moves by a factor of 1.

In the first illustration below, when fast points to node 6, slow will be pointing to node 3. When slow moves one step ahead, it will point to node 4. At the same time, fast moves two nodes ahead, 6 -> 3 -> 4. Hence, it will also point to node 4. Since both slow and fast now point to the same node, we conclude that we have detected a cycle in this linked list.

Dry-run templates

Consider the following algorithm for detecting a cycle in a linked list:

Press + to interact
Python 3.5
class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next
def has_cycle(head):
  slow, fast = head, head
  while fast is not None and fast.next is not None:
    fast = fast.next.next
    slow = slow.next
    if slow == fast:
      return True  # found the cycle
  return False
def main():
  head = Node(1)
  head.next = Node(2)
  head.next.next = Node(3)
  head.next.next.next = Node(4)
  head.next.next.next.next = Node(5)
  head.next.next.next.next.next = Node(6)
  head2 = Node(1)
  head2.next = Node(2)
  head2.next.next = Node(3)
  head2.next.next.next = Node(4)
  head2.next.next.next.next = Node(5)
  head2.next.next.next.next.next = Node(6)
  head2.next.next.next.next.next.next = head2.next.next
  input = [head, head2]
  for i in input:
    print("LinkedList has cycle: " + str(has_cycle(i)))
main()

To help students understand how the solution works, they may be encouraged to run through the provided solution with the following sample inputs:

Sample input #1

1 -> 2 -> 3 -> 4 -> 5 -> 6

Iteration number

Line number

head

slow

fast

-

8

1

1

1

1

9 - 13

1

2

3

2

9 - 13

1

3

5

3

9 - 13

1

4

None

Visualise the above example with the help of the following slide deck:

Sample input #2

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 3

Iteration number

Line number

head

slow

fast

-

8

1

1

1

1

9 - 13

1

2

3

2

9 - 13

1

3

5

3

9 - 13

1

4

3

4

9 - 13

1

5

5

Trace generation

The algorithm to find a cycle in a linked list is pretty straightforward. We have two pointers that traverse through the given list at different speeds. If at any point, both pointers point to the same node, we have a cycle.

Let’s visualize this below:

Press + to interact
Python 3.5
class LinkedList:
  def __init__(self):
      self.head = None
      self.last = 0 # the point where the cycle starts,
      self.back = 0 # how many nodes back into the list does the last "actual" node point?
  def __str__(self):
    temp = self.head
    i = 0
    out = ""
    while temp is not None and i < (self.last + self.back + 1):
      i += 1
      out += str(temp.value) + " "
      
      temp = temp.next
      if temp is None:
        out += "--> None"
      else:
        if i == self.last:
          out += "--≫ " # our meta information helps us to indicate where the cycle starts
        elif i == (self.last + self.back + 1):
          out += "--≫ (...)" # again using meta information to indicate that the pattern will repeat beyond this point
        else: 
          out += "--> " 
    return out
class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next
def has_cycle(lst):
  slow, fast = lst.head, lst.head
  print("Head pointer: ", lst.head.value, sep = "")
  print("Slow pointer: ", slow.value, sep = "")
  print("Fast pointer: ", fast.value, sep = "")
  i, j = 0, 0
  print(str(lst))
  print(" "*((6*i)) + "ŝf̂")
  while fast is not None and fast.next is not None:
    # print(str(lst))
    print("\n\tLoop index:", i)
    # print("Slow pointer: ", slow.value)
    # print("Fast pointer: ", fast.value, "\n")
    fast = fast.next.next
    slow = slow.next
    j+=2
    i+=1
    print("\tAfter advancing:\n\tSlow pointer:", slow.value)
    if fast == None:
      print("\tFast pointer: None\n")
      j = lst.last
    else:
      print("\tFast pointer:", fast.value, "\n")
    print("\t", str(lst), sep="")
    if slow == fast:
      print("\t", " "*((6*i)), "ŝf̂", sep="")
      print("\tBoth slow and fast pointers are pointing to the same node. A cycle has been detected!")
      return True  # found the cycle
    else:
      print("\t", " "*(6*i) + "ŝlow", " "*((6*(j-1))-((6*i)-2)), "f̂ast", sep="")
  return False
def main():
  head = Node(1)
  head.next = Node(2)
  head.next.next = Node(3)
  head.next.next.next = Node(4)
  head.next.next.next.next = Node(5)
  head.next.next.next.next.next = Node(6)
  lst1 = LinkedList()
  lst1.head = head
  lst1.last = 6
  lst1.back = 0
  head2 = Node(1)
  head2.next = Node(2)
  head2.next.next = Node(3)
  head2.next.next.next = Node(4)
  head2.next.next.next.next = Node(5)
  head2.next.next.next.next.next = Node(6)
  head2.next.next.next.next.next.next = head2.next.next
  lst2 = LinkedList()
  lst2.head = head2
  lst2.last = 6
  lst2.back = 3
  inputs = [lst1, lst2]
  for i in range(len(inputs)):
    print("Checking cycles in linked list:", str(inputs[i]))
    print("Linked list has cycle:", str(has_cycle(inputs[i])))
    print("-"*100, "\n", sep="")
main()

Here’s what we’re doing in the above code:

  • Line 33: Initially set both slow and fast pointers to the head of the linked list.
  • Line 45: Since we want to move fast by a factor of 22 compared to slow, in each iteration, we move it two nodes ahead.
  • Line 46: Move slow one node ahead.
  • Line 50: Since fast is moving ahead of the slow pointer, it will reach the end of the linked list faster. If it becomes None, this means that there’s no cycle in the linked list.
  • Line 56: If at any point slow becomes equal to fast, there’s a cycle present.