DSA Visualizations | Hello Interview

Linked List Cycle

DESCRIPTION (credit Leetcode.com)

Write a function that takes in a parameter head of type ListNode that is a reference to the head of a linked list. The function should return True if the linked list contains a cycle, and False otherwise, without modifying the linked list in any way.


# Definition of a ListNode
class ListNode:
  def __init__(self, value=0, next=None):
    self.value = value
    self.next = next

EXAMPLES

Example 1:

Output: true, there is a cycle between node 0 and node 3.

Example 2:

Output: false, there is no cycle in the linked list.

We recommend taking some time to solve the problem on your own before reading the solutions below.

Solutions

1. Keep Track of Visited Nodes

One approach to this problem is to keep a set of visited nodes while iterating through the linked list. At each node, we check if the node exists in the set. If it does, then the linked list contains a cycle. If it doesn't, we add the node to the set and move to the next node. If we reach the end of the linked list without encountering a node in the dictionary, then the linked list does not contain a cycle.


class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

def hasCycle(head):
  visited_nodes = set()

  current_node = head
  while current_node is not None:
    if current_node in visited_nodes:
      return True  # Cycle detected

    visited_nodes.add(current_node)
    current_node = current_node.next

  return False

Time Complexity: O(n), where n is the number of nodes in the linked list. In the worst case scenario, the algorithm visits each node once. Space Complexity: O(n), where n is the number of nodes in the linked list. The space complexity is due to the set storing visited nodes.

2. Optimal Solution: Fast and Slow Pointers

The approach above requires O(n) space to store each visited node in the set. A more optimal solution solves this problem without using additional space (i.e. constant, O(1) space) by using fast and slow pointers.

This approach starts by initializing two pointers, fast and slow at the head of the list. It then iterates over the linked list, and in each iteration, the slow pointer advances by one node, while the fast pointer advances by two nodes.

Detecting a Cycle

If the linked list contains a cycle, the fast pointer will eventually overlap the slow pointer, and both pointers will point to the same node.

initialize pointers

0 / 4

When the list contains a cycle, fast and slow eventually meet at the same node.

No Cycle

When there is no cycle, the fast pointer reaches the tail of the linked list, where fast.next = None (step 3 in the animation below). This is enough to determine the linked list does not contain a cycle.

initialize pointers

0 / 3

If there is no cycle, eventually fast.next = None

When there is no cycle and the linked list has an even number of nodes, eventually fast = None (step 2 in the animation below).

initialize pointers

0 / 3

Even # of nodes and no cycle, eventually fast.next = None

Putting it all together, our algorithm involves the following steps:

Initialize fast and slow pointers at the head of the linked list.
Iterate over the linked list. Each iteration advances slow by one node and fast by two nodes.
If the fast pointer reaches the end of the linked list (either fast.next = None or fast = None), then the linked list does not contain a cycle.
If the fast and slow pointers meet at the same node (fast == slow), then the linked list contains a cycle.

Code

To construct the linked list that is used in the animation below, provide a list of integers nodes and an integer tail. Each integer in nodes is used as the value of a node in the linked list, and the order of the integers in the list will be the order of the nodes in the linked list.

The tail integer is the index of the node that the last node in the linked list points to form a cycle. If there is no cycle, set tail = -1.


class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

def hasCycle(head):
  slow = head
  fast = head

  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
      return True

  return False

linked list cycle

0 / 5

Edge Cases

Empty List

When the linked list is empty, fast = None to start, the while loop never runs and the function returns False.


class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

def hasCycle(head):
  slow = head
  fast = head

  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
      return True

  return False

linked list cycle

0 / 2

nodes = [], tail = -1

Single Node (No Cycle)

When the linked list contains a single node without a cycle, fast.next = None to start and the function returns False without running the while loop.


class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

def hasCycle(head):
  slow = head
  fast = head

  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
      return True

  return False

linked list cycle

0 / 2

nodes = [1], tail = -1

Single Node (with Cycle)

When the linked list contains a single node with a cycle, slow.next and fast.next.next point to the same single node, and the function returns True during the first iteration of the while loop.


class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

def hasCycle(head):
  slow = head
  fast = head

  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
      return True

  return False

linked list cycle

0 / 3

nodes = [1], tail = 0

Worst Case Scenario

In the worst case scenario, the fast pointer traverses the entire list twice before meeting the slow pointer.


class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

def hasCycle(head):
  slow = head
  fast = head

  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
      return True

  return False

linked list cycle

0 / 6

nodes = [5, 4, 3, 2], tail = 0

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the linked list. In the worst case scenario, the fast pointer traverses the linked list twice, and the slow pointer traverses the linked list once, regardless of the number of nodes in the linked list.

Space Complexity: O(1), as we only use two pointers to traverse do our traversal, which does not change with the number of nodes in the linked list.

Next: Palindrome Linked List

Your account is free and you can post anonymously if you choose.

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Overview

Palindrome Linked List

Linked List Cycle

DESCRIPTION (credit Leetcode.com)


# Definition of a ListNode
class ListNode:
  def __init__(self, value=0, next=None):
    self.value = value
    self.next = next

EXAMPLES

Example 1:

Output: true, there is a cycle between node 0 and node 3.

Example 2:

Output: false, there is no cycle in the linked list.

We recommend taking some time to solve the problem on your own before reading the solutions below.

Solutions

1. Keep Track of Visited Nodes


class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

def hasCycle(head):
  visited_nodes = set()

  current_node = head
  while current_node is not None:
    if current_node in visited_nodes:
      return True  # Cycle detected

    visited_nodes.add(current_node)
    current_node = current_node.next

  return False

2. Optimal Solution: Fast and Slow Pointers

Detecting a Cycle

If the linked list contains a cycle, the fast pointer will eventually overlap the slow pointer, and both pointers will point to the same node.

initialize pointers

0 / 4

When the list contains a cycle, fast and slow eventually meet at the same node.

No Cycle

initialize pointers

0 / 3

If there is no cycle, eventually fast.next = None

When there is no cycle and the linked list has an even number of nodes, eventually fast = None (step 2 in the animation below).

initialize pointers

0 / 3

Even # of nodes and no cycle, eventually fast.next = None

Putting it all together, our algorithm involves the following steps:

Initialize fast and slow pointers at the head of the linked list.
Iterate over the linked list. Each iteration advances slow by one node and fast by two nodes.
If the fast pointer reaches the end of the linked list (either fast.next = None or fast = None), then the linked list does not contain a cycle.
If the fast and slow pointers meet at the same node (fast == slow), then the linked list contains a cycle.

Code

The tail integer is the index of the node that the last node in the linked list points to form a cycle. If there is no cycle, set tail = -1.


class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

def hasCycle(head):
  slow = head
  fast = head

  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
      return True

  return False

linked list cycle

0 / 5

Edge Cases

Empty List

When the linked list is empty, fast = None to start, the while loop never runs and the function returns False.


class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

def hasCycle(head):
  slow = head
  fast = head

  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
      return True

  return False

linked list cycle

0 / 2

nodes = [], tail = -1

Single Node (No Cycle)

When the linked list contains a single node without a cycle, fast.next = None to start and the function returns False without running the while loop.


class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

def hasCycle(head):
  slow = head
  fast = head

  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
      return True

  return False

linked list cycle

0 / 2

nodes = [1], tail = -1

Single Node (with Cycle)

When the linked list contains a single node with a cycle, slow.next and fast.next.next point to the same single node, and the function returns True during the first iteration of the while loop.


class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

def hasCycle(head):
  slow = head
  fast = head

  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
      return True

  return False

linked list cycle

0 / 3

nodes = [1], tail = 0

Worst Case Scenario

In the worst case scenario, the fast pointer traverses the entire list twice before meeting the slow pointer.


class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

def hasCycle(head):
  slow = head
  fast = head

  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
      return True

  return False

linked list cycle

0 / 6

nodes = [5, 4, 3, 2], tail = 0

Complexity Analysis

Space Complexity: O(1), as we only use two pointers to traverse do our traversal, which does not change with the number of nodes in the linked list.

Next: Palindrome Linked List

Your account is free and you can post anonymously if you choose.

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103