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 -> nilOutput:
false -
Example 2
Input:
Potato Jack -> Potato George -> Potato Arthur ↑ ↓ ← ← ← ← ← ← ← ← ←Output:
true
Solution 💡
We use two pointers:
slowNodemoves one node at a time.
fastNodemoves two nodes at a time.-
As we iterate through the list:
If
fastNodereaches the end (nil), there’s no cycle.If
slowNodeandfastNodemeet 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
Asparagos | Sciencx (2025-07-14T09:00:54+00:00) Asparagos vs Potato Bugs: Can He Detect the Cycle in O(1) Space?. Retrieved from https://www.scien.cx/2025/07/14/asparagos-vs-potato-bugs-can-he-detect-the-cycle-in-o1-space/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.