Linked List Cycle

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

// class ListNode {
//     int val;
//     ListNode next;
// }

public class Solution {
    public Boolean hasCycle(ListNode head) {
        // Your code goes here
    }
}

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.

import java.util.*;
class ListNode {
    int val;
    ListNode next;
    
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { 
        this.val = val; 
        this.next = next; 
    }
}
public boolean hasCycle(ListNode head) {
    Set<ListNode> visitedNodes = new HashSet<>();
    ListNode currentNode = head;
    while (currentNode != null) {
        if (visitedNodes.contains(currentNode)) {
            return true;  // Cycle detected
        }
        visitedNodes.add(currentNode);
        currentNode = currentNode.next;
    }
    return false;
}

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.

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.

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

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

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}
public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

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 {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}
public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

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 {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}
public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

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 {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}
public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

Worst Case Scenario

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

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}
public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}