1. Detect whether a linked list contains a cycle.
Given a linked list, determine whether it contains a cycle.
I use Floyd’s cycle detection. I keep two pointers on the linked list. The slow pointer moves one node at a time, and the fast pointer moves two nodes at a time. If the list has a cycle, the fast pointer will eventually meet the slow pointer inside the loop. If the fast pointer reaches null, there is no cycle. I stop as soon as they meet or the end is reached. This runs in O(n) time and O(1) extra space.
See the Code while reading this explanation.
This question asks whether a linked list ever loops back to an earlier node. In the diagram, the list is 1 -> 2 -> 3 -> 4 -> 5, and node 5 points back to node 3. That means the answer is true. I use two pointers. One moves one step. The other moves two steps. If they meet, the list has a cycle. If the fast pointer reaches the end, the list has no cycle. This is a good fit because it checks the list without extra storage.
- Should I return only true or false, or also the node where the cycle starts?
- Can I keep the list unchanged and use constant extra space?
The input is one linked list head. The output is a boolean. The diagram uses one example list: 1 -> 2 -> 3 -> 4 -> 5, with 5 linking back to 3. The expected result is true because the list contains a cycle.
I use two pointers, slow and fast. slow moves by one node. fast moves by two nodes. The key invariant is that if a cycle exists, fast will eventually lap slow and they will meet inside the loop. This is better than saving visited nodes because it uses constant extra space.
Both slow and fast start at head. That matches step 0 in the diagram. The loop continues only while fast and fast->next are not null. This keeps the code safe when the list has no cycle.
Step 1: slow goes to 2 and fast goes to 3. Step 2: slow goes to 3 and fast goes to 5. Step 3: slow goes to 4 and fast goes to 4. They meet, so the code returns true right away. We do not process any later step.
If there is no cycle, fast eventually reaches null. If there is a cycle, fast keeps moving around the loop and eventually catches slow. That is why meeting means the list contains a cycle.
The function takes ?ListNode $head. It sets both pointers to head. Inside the loop, slow moves one step and fast moves two steps. If slow === fast, it returns true immediately. If the loop ends, it returns false. The code compares node references, not node values.
Time is O(n). Extra space is O(1). Important edge cases are an empty list, one node with no cycle, one node that points to itself, and two nodes with or without a cycle.
The central invariant is simple. slow moves one step and fast moves two steps over the same next pointers. If there is a cycle, fast will lap slow and they will meet. If there is no cycle, fast reaches null first. This is why we do not need a visited set. The diagram’s example shows the meet at the node with value 4 after the cycle at node 3 is entered.
<?php
declare(strict_types=1);
class ListNode
{
public int $val;
public ?ListNode $next;
public function __construct(int $val = 0, ?ListNode $next = null)
{
$this->val = $val;
$this->next = $next;
}
}
/**
* Detect whether a linked list contains a cycle.
*/
function hasCycle(?ListNode $head): bool
{
// Start both pointers at the head node.
$slow = $head;
$fast = $head;
// Move until the fast pointer reaches the end or the two pointers meet.
while ($fast !== null && $fast->next !== null) {
// slow moves one step.
$slow = $slow->next;
// fast moves two steps.
$fast = $fast->next->next;
// If both pointers point to the same node, a cycle exists.
if ($slow === $fast) {
return true;
}
}
// No cycle was found.
return false;
}
// Demo example from the diagram:
// 1 -> 2 -> 3 -> 4 -> 5
// ^ |
// |____|
$node1 = new ListNode(1);
$node2 = new ListNode(2);
$node3 = new ListNode(3);
$node4 = new ListNode(4);
$node5 = new ListNode(5);
$node1->next = $node2;
$node2->next = $node3;
$node3->next = $node4;
$node4->next = $node5;
$node5->next = $node3;
var_dump(hasCycle($node1)); // bool(true)The list is processed with two pointers. Each loop step does constant work. The loop stops when the fast pointer reaches the end or when slow and fast meet. So the time is O(n). We only store two pointers, so the extra space is O(1).
This pattern is useful whenever a next-pointer chain could loop back to an earlier node. Common examples are linked list interview problems and any pointer chain where a cycle would cause an endless loop.
The interviewer wants to see whether I can recognize Floyd’s cycle detection, use node references correctly, and explain why two speeds prove the cycle. They also want to check safe PHP null handling, early return, constant extra space, and whether I can keep node identity separate from node value.
A common mistake is comparing node values instead of node identity. Another is skipping the null check before moving fast two steps. Another is moving the wrong pointer by the wrong amount. Another is forgetting to return as soon as the pointers meet. Some candidates also add extra storage even though this problem can be solved with two pointers only.
Say the invariant out loud: slow moves one step, fast moves two, and meeting means there is a cycle.
