Asparagos vs Potato Bugs: Can He Detect the Cycle in O(1) Space?

This content originally appeared on DEV Community and was authored by Asparagos

Potato vs Bugs. Can FIFO save the harvest?

Hi! I’m Asparagos — an asparagus who codes in Go. Here you’ll find everyday problems that a typical veggie might struggle with — and my Go solutions to them. Today we are solving the problem of Potato Bugs .

Problem

Yet another challenging day in the Veggie Kingdom. To save the harvest, all potatoes must be treated for bugs. That’s why they’re lining up at the Fight for Insect-Free Organics (FIFO) office.

But potatoes aren’t the sharpest veggies — they might mess things up and accidentally form a cycle in the queue. We need to check whether their queue contains a cycle.

The Kingdom is going through hard times, so we must solve this using only constant memory.

Input

A head of a linked list of potatoes. Each potato has a Name and a pointer to the next one:

type PotatoNode struct {
    Name string
    Next *PotatoNode
}

Output

Return true if the list contains a cycle, or false otherwise.

Examples :

• Example 1

  Input:
  

  Potato Jack -> Potato George -> Potato Arthur -> nil
  

  Output: false

• Example 2

  Input:
  

  Potato Jack -> Potato George -> Potato Arthur
                        ↑                ↓
                        ← ← ← ← ← ← ← ← ←
  

  Output: true

Solution

1. We use two pointers:
   slowNode moves one node at a time.
   fastNode moves two nodes at a time.

2. As we iterate through the list:

   If fastNode reaches the end (nil), there’s no cycle.

   If slowNode and fastNode meet at the same node, it means there’s a cycle.
   

func hasPotatoCycle(head *PotatoNode) bool {
    if head == nil {
        return false
    }
    slowNode := head
    fastNode := head
    for fastNode != nil && fastNode.Next != nil {
        slowNode = slowNode.Next
        fastNode = fastNode.Next.Next
        if slowNode == fastNode {
            return true
        }
    }
    return false
}

This is a classic example of Floyd’s cycle-finding algorithm, also known as the Tortoise and Hare algorithm.

Naturally, no tortoises or hares were allowed to participate in our event – otherwise, our veggies would’ve been in serious danger.

Feel free to check out the full code with tests on GitHub, and don’t hesitate to leave a if you find it helpful!

This content originally appeared on DEV Community and was authored by Asparagos