A singly linked list is built with a bunch of nodes. Each node pointing to the next one in the sequence. If your list gets caught in a cycle, where a node in your list points to a node in an earlier part of the list. You may have some issues, unless you enjoy going in circles, endlessly……. I didn’t think you did, so let’s take a look at how we’d spot a cycle in a list and make big-O considerations for both runtime and space cost.

Identify the key limits of the problem

If a cycle exists in our linked list we need to know where in the list it starts. Do so we would need to go through the entire linked list at least 1 to determine where each element points. Best case scenario, you go straight to the end of the list and point to nil/null. With no cycles, just linearly connected nodes, we are looking at O(n) best case run time for this algorithm.

What about space considerations? We can do a number of different things to determine where each node is pointing to. This will ultimately determine our space cost upper bound.

Brute Force — Race through the linked list maze and mark each move

I’m going to assume we know the number of nodes in our list. It shouldn’t be very difficult to comprehend so we’ll just dive into the code.

Node = Struct.new(:value, :next)
... build linked list of Node objects ...
def contains_cycle?
    node = @root  #@root is our first node in the sequence
    next_node = node.next
    counter = 0
    node_array = []
    while counter < @node_count
      return true if node_array.include?(node.next.object_id)
      node_array.push(node.object_id)
      next_node = node.next
      node = next_node
      counter += 1
    end
    false
  end

We’ll take our list and traverse it until we have gone through it for the length of the list. It will return true if our array of node object ids contains the node that is being pointed to next. This has O(n) space cost because we are creating an array that is the same size as the list itself in the worst case, which is the case where we cycle from the tail of the list back to the head of the list. There’s got to be a way we can do this with O(1) space costs though. Shall we….?

Partner for success

Have you ever parked your car in a massive parking lot with no indicators? You know that feeling of seeing things over and over and wondering if you already checked there? Well searching a linked list is much the same. To help you get out of that situation you could definitely use a friends help.

She can stay at some agreed upon place as you go traipsing through the parking lot. If you come across her after some time, you can face-palm yourself, then continue out another way. But what if you get turned around somewhere far from her. You go in circle after circle but she’s no where to be found. This strategy won’t work. It’s similar to cycling in your list somewhere other than the root node. Alright that idea is out and we need to rethink our inks.

Ok, how about this. Both you and her start traversing the parking lot together. You go on and skip over every other row of cars. You are confident enough that you can see over a row of cars and spot your car. So, no worries. Now she can take her time and be the steady one, going one row at a time. If you happen to stumble back on her as you are going, you know you circled back. Remember she is the reliable one, and knows where she has been. **Cough**, **Cough**, it seems you found a cycle in your car search. How can we do this in our linked list problem? Let’s take a looksy.

def contains_cycle?
    doubler = @root   #move two nodes at a time
    single = @root    #move one node at a time
    while doubler != nil && doubler.next != nil
      single = single.next
      doubler = doubler.next.next
      return true if doubler == single
    end
    false
  end

Notice that our space costs is a minimal O(1) in this implementation. We are not storing any information from every node. In fact we are only checking to see if our doubler ever meets back up with our single. Meeting up again can only happen if there is a cycle in our list. Otherwise the doubler will get to the end of the list and we’ll have absolute certainty that we have no cycles.