Floyd’s Cycle Detection Algorithm

I just spent half a day trying to wrap my brain around how to detect cycles within linked lists, as well as how to find the first node of the cycle. After perusing all the Stack Overflow and Wikipedia entries, I had a pretty good mechanical understanding of the most elegant solution, which is known as Floyd’s Cycle-Finding Algorithm, or more informally, the tortoise and the hare algorithm.

The problem with my mechanical understanding was that it’s a classic case of surface-level learning, the kind of sloppy, rote-memorization cramming that somehow powered me through UCI to a 3.2 GPA but left me utterly uninterested and disengaged from my craft. I’d perform well if an interviewer asked me that question tomorrow, but I’d feel like a charlatan if I only parroted an answer back at him. Just because I flipped through some old tome and found an incantation that allowed me to cast a black magic wizard spell doesn’t make me Harry Potter.

I wanted an intuitive understanding of the solution. If I have that, I will carry it for the rest of my life.

In the name of that pursuit, I sat down and turned that problem over and over through my head until I found an elegant way to visualize and understand the reason behind the math. Since it’s an approach I wish I’d thought of six hours ago, I want to share it.

First off, let’s assume everyone knows what a linked list is. I’m talking about your standard, garden-variety singly linked list: it has a head pointer but no tail pointer, made up of nodes that contain a pointer to the next node in the list (except for the last node, which points to null).

Drawing1

A linked list with a cycle in it has one or more nodes that point to a previous node in the list. If you traverse the node starting from the head, you’ll get caught in the cycle loop.

Drawing2

Did you ever play Super Mario Bros. 1? On the Level 8 and 9 dungeons, if you didn’t go the right path, you would cycle backwards until you did. It’s sort of like that.

The Floyd Cycle Detection Algorithm works by using two pointers, one slow and one fast. We’ll call them the tortoise and the hare, respectively. They start at the first node.

Drawing3

The hare travels 2 nodes per move, and the tortoise travels 1 node per move.

Drawing4

Drawing5

Drawing5a

And so on. If the hare pointer meets the tortoise pointer, you’ve got yourself a cycle:

Drawing5c

To visualize why this works, let’s go back to our Mario analogy. Imagine you could play a co-op two-player mode of those cycle-containing dungeons. If Luigi always moved slower than Mario, and Mario keeps hitting the cycle part of the dungeon, Mario will at some point pass Luigi.

But why do we choose to go 2 nodes per move? Couldn’t you go 3 nodes per move? Well, yes, you could, but it’s not important how fast the hare goes. The hare could go light speed for all we care, but it can only pass the tortoise once the tortoise reaches the cycle.

There are some interesting properties about this algorithm:

  • The hare is always twice as many steps ahead of the tortoise (if an interviewer asks you how to find the middle of a linked list, have the hare run off the end of your list and the tortoise will be at exactly the middle)
  • The hare can never “skip” over the tortoise without them first sharing the same node. It seems like it might because it moves in chunks of two, but remember that for each step, the hare only gains one node on the tortoise.

Now that we can detect cycles, the next step is figuring out where the cycle starts and how to fix the cycle. This is where it gets tricky.

All of the Stack Overflow answers talk about the tortoise being Xi, the hare being X2i, and lambda (the length of the cycle) and mu (the number of steps to get to the cycle).

Let’s toss that all aside and agree upon this: the hare has always taken twice as many steps as the tortoise, right? Right.

So the tortoise and the hare meet at a particular node for the first time. The tortoise has entered the cycle but hasn’t done a full loop. The hare, depending on the size of the list and the cycle, may have done the loop only once, or it could have done the loop a million times. However, no matter how many times the poor hare has been spun through the cycle, we can guarantee that it has traveled twice as many steps as the tortoise has.

Drawing6

Again, that’s very important. It means that at that meeting point node, if the tortoise has taken i steps, and if the tortoise takes another i steps (i + i = 2i), it will end up at that same node. If it’s a big loop, it’ll only have to loop once, but if it’s a tight loop, it might go through it a lot of times, just like the hare had to do. But no matter what, we can guarantee that it’ll end up on the meeting node after i steps.

So here’s the heart and soul of Floyd’s Cycle Detection Algorithm: if we cloned the tortoise and placed one at the head of the list and one at the meeting point node, if we had them take i steps, we would guarantee that they would reach the meeting point node at the same time. Why? Because the cloned tortoise starts at position i and takes i steps, which makes a total distance of 2i.

But think about it: they wouldn’t just meet at the meeting point node, they would meet for all of the nodes at the beginning of the cycle until they reached the meeting point node. In fact, it means that the very first node that they meet is the very first node of the cycle.

Once we know the first node of the cycle, fixing the cycle is trivial: plop down a pointer to this first node, and use another pointer to traverse the rest of the cycle until you reach the node who points at the first node.

Eating as a metaphor for productivity

I’ve been thinking about diet as a metaphor for the things I do every day. There are good and bad things I can eat, the same way that there are productive tasks that nourish my life as well as unproductive or even harmful things that diminish me.

Lean meats and vegetables are equivalent to work, study, organization, errands. Fruits might be enjoying the company of friends and loved ones, or working on a fun hobby. Watching TV might be a nice rack of BBQ ribs, and sitting on the couch playing video games like a zombie would be akin to stuffing doughnut after doughnut down your gullet.

Lately, I’ve noticed that keeping a steady, monotonous diet of one or two foods will kill my appetite. I eat less overall. This matches pretty closely with a study that shows a correlation between increased variety of foods and greater food consumption.

It seems to be the same with my daily tasks. If I spent all day watching TV (which I wouldn’t), I’d feel sick in the same way I’d feel after cleaning out a bucket of ice cream. If I worked and studied all day, I’d feel healthy and proud of myself the same way I would if I’d eaten lean meats and fibrous vegetables, but I’d also be dreaming about that bucket of ice cream.

The problem is that too much of one thing will kill my appetite for that thing. That’s not a problem with ice cream, since I don’t want to overeat empty calories or watch TV all day. However, if I want to be very productive at one thing (e.g. convert ColorMyWorld to iOS 7), eventually I get fatigued of the lack of variety, which isn’t too dissimilar from eating grilled chicken breast day-in, day-out.

I think the best productivity hack to keeping a healthy diet is to keep a wide variety of foods so that you don’t get tired or bored of any one meal. Different proteins, different preparations, different sauces, different vegetables. There’s room for fruit, of course; that’s important. There’s also room for occasional indulgences, if only to give yourself a mental break and not feel deprived. But if you want to eat healthy foods consistently, you can’t let yourself get bored, frustrated, or tired of healthy foods.

I’m feeling the same way about work and productivity. Doing one task for eight hours will fatigue anyone. I’ve found that switching between different productive tasks is a great way to keep productivity up while combating monotony. It’s important that I don’t get sick of ColorMyWorld, so I might switch to interview questions or learn about Auto Layout or watch Coursera lectures.

A mindset for progress

I’m learning the value of plugging away on a task without judgment instead of obsessing about progression.

Progression isn’t linear. Some problems remain shrouded in a thick fog until you put in the time and work, and suddenly the fog is lifted and you break through to a new level of understanding.

If you’re worried about your progress or lack thereof, you won’t have the patience to wait for the breakthrough.

This Coursera class on Algorithms that I’m taking is a good example. It’s a tough version of a basic course on algorithms and data structures, and not so different from the one I took at UCI a decade ago except that the video game difficulty setting has been jacked up a few notches. A lot of the exercise problems I’m facing are novel in presentation and concept.

Thankfully, I’m armed with the best that Adam Robinson, Toni Krasnic, and the XMind mind mapping software have to offer, and putting in the effort is easier when there’s a framework that you can put your faith into. Yes, I have faith in these systems, and these systems have empowered me to take control of my own education.

Instead of forcing myself to memorize how to use a union-find data structure, I ask myself a series of questions. What is this data structure trying to solve? What’s the naive approach? What are some optimizations? How might I use this in other situations? On and on, I ask myself better questions and am rewarded with better answers. I map these concepts, stare at them, ask more questions, draw relationships, and constantly edit and reorganize until they make sense. I flex those muscles with exercises, and reinforce them after some time has passed.

It works, oh miracle of miracles, it does. I wish I’d known earlier that learning is about asking good questions, wanting good answers, and having the mindfulness and patience to enjoy the ride. Still, I’m thankful that I know now what I couldn’t before.

These days I don’t experience much dread when I run into an obstacle, I experience bemusement. “How will I get past this,” I wonder. And off I go.