Skip to content

Detecting Cycles in a Linked List in Python

Updated: at 03:34 AM

Linked lists are common data structures used in many algorithms and applications. They consist of nodes that contain data and a reference (or pointer) to the next node in the list. Unlike arrays, linked lists do not store data contiguously in memory, allowing for efficient insertion and removal of nodes.

A key question that arises with linked lists is whether they contain cycles, where a node’s next reference points back to an earlier node, creating a loop in the list. Detecting cycles is important for several reasons:

In this comprehensive Python programming guide, you will learn approaches to detect cycles in a linked list. The step-by-step instructions provided include example code and explanations of the key concepts. By the end, you will be able to implement efficient solutions to this common technical interview question using Python.

Table of Contents

Open Table of Contents


To fully understand this guide, you should have:

The examples will use a simple Node class to represent each element in the linked list:

class Node:
  def __init__(self, data): = data = None

The data attribute stores the node’s data, while next points to the following node.

Approach 1: Hash Table

The hash table approach keeps track of nodes seen while traversing the linked list. If a node is seen more than once, a cycle must exist. The steps are:

  1. Initialize a hash table or set to store seen nodes.

  2. Traverse the linked list from the head node.

  3. For each node, check if it is in the hash table.

  4. If not, add it and move to the next node.

  5. If it already exists in the hash table, a cycle is present.

Here is Python code implementing this technique:

# Initialize hash table
seen = set()

current = head
while current:
  # Check if node exists
  if current in seen:
    return True # Cycle detected

  # Add to hash table

  # Move to next node
  current =

return False # No cycle detected

The time complexity is O(N) since each node is visited at most once. The space complexity is O(N) for the hash table storing N nodes.

Hash Table Approach Pros and Cons



Approach 2: Two Pointers

The two pointer technique checks for a cycle by using 2 pointers traversing the list at different speeds. If the linked list has a cycle, the pointers will eventually meet inside the cycle.

The steps for this approach are:

  1. Initialize two pointers - slow and fast

  2. Increment slow by 1 node, fast by 2 nodes

  3. If fast encounters a null node, no cycle exists

  4. If slow and fast meet, a cycle is present

  5. To find the start node, increment a pointer from head and another from meeting node until they collide

Here is the Python implementation:

def has_cycle(head):

  # Initialize slow and fast pointers
  slow, fast = head, head

  while fast and

    # Increment slow by 1, fast by 2
    slow =
    fast =

    # Check if pointers meet
    if slow == fast:
      return True

  # fast reached null, so no cycle
  return False

# If cycle found, find start node by incrementing
# pointer p1 from head, and p2 from meeting point
def start_node(head):

  # Check for cycle
  if not has_cycle(head):
    return None

  # Initialize p1 from head, p2 from meeting point
  p1 = head
  p2 = head

  # Increment p1 by 1, p2 by 1 until they collide
  while p1 != p2:
    p1 =
    p2 =

  # Return start node
  return p1

The time complexity is O(N) to detect a cycle and O(N) to find the start node. Only two pointers are used, so the space complexity is O(1).

Two Pointer Approach Pros and Cons



Approach 3: Set Node Values

This technique modifies node values as the list is traversed. The steps are:

  1. Initialize variable value to 0

  2. Traverse list and set node values to value

  3. Increment value after setting each node

  4. If a node with value already set is found, a loop exists

Here is Python code for this algorithm:

value = 0

current = head
while current:

  # Cycle exists if node value
  # already changed
  if == value:
    return True

  # Set node value = value

  # Increment for next node
  value += 1

  current =

return False # No cycle

By changing node values, we can detect if a node has been visited before. The time complexity is O(N) to visit each node once. The space used is O(1).

Set Values Approach Pros and Cons



This recursive algorithm traverses the graph depth-first, keeping track of visited nodes. If a node is visited more than once, there is a cycle.

Here are the steps:

  1. Create a visited set to track visited nodes

  2. Define recursive DFS function accepting current node

  3. Mark node visited and recursively call DFS on adjacent unvisited nodes

  4. If node was already visited, return True for cycle

  5. Return False if all nodes are visited once

And here is a Python implementation:

visited = set()

def dfs(node):

  # Visited before, cycle exists
  if node in visited:
    return True

  # Add to visited

  # Recursively visit adjacent nodes
  for n in node.nexts:
    if dfs(n):
      return True

  # No cycle detected
  return False

# Start at head node
return dfs(head)

The time complexity is O(N) since each node is visited once. The space used for the visited set is O(N).

Recursive DFS Pros and Cons



Comparing Approaches

ApproachTime ComplexitySpace ComplexityFinds Cycle StartIn-place
Hash TableO(N)O(N)NoNo
Two PointersO(N)O(1)YesYes
Set ValuesO(N)O(1)NoYes
Recursive DFSO(N)O(N)NoYes

So in summary, the two pointer approach provides the best combination of low overhead, good performance, and ability to find the cycle start node.


Detecting linked list cycles has many useful applications:


This guide covered 4 techniques to determine if a cycle exists in a linked list using Python:

The two pointer approach provides an optimal combination of speed, low overhead, and ability to find the node where the cycle originates. Linked list cycle detection is an important technique for writing robust code and improving applications like debugging, garbage collection, web crawling, and more.

By mastering these algorithms in Python and understanding their trade-offs, you will be prepared to efficiently handle this common technical interview question and tackle linked list cycle scenarios in your own programs.