Linked List Cycle

Linked List Cycle

What is this problem about?

The "Linked List Cycle interview question" is a classic computer science problem. Given the head of a linked list, you need to determine if the list contains a cycle. A cycle occurs if there is some node in the list that can be reached again by continuously following the next pointer. This "Linked List Cycle coding problem" is the introductory challenge for cycle detection algorithms.

Why is this asked in interviews?

This is one of the most frequently asked questions at companies like Google, Amazon, and Microsoft. It tests a candidate's understanding of the "Linked List interview pattern" and their ability to optimize space complexity. While a hash table can solve this, interviewers are usually looking for the "Two Pointers interview pattern" solution, which uses O(1) extra space.

Algorithmic pattern used

The primary pattern is "Floyd's Tortoise and Hare" (Cycle-Finding Algorithm). You use two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. If there is a cycle, the fast pointer will eventually "lap" the slow pointer and they will meet at the same node. If the fast pointer reaches the end of the list (null), then no cycle exists.

Example explanation

List: 3 -> 2 -> 0 -> -4, and -4 points back to 2.

1. Step 1: Slow at 3, Fast at 2.
2. Step 2: Slow at 2, Fast at -4.
3. Step 3: Slow at 0, Fast at 0 (Fast moved from -4 to 2 to 0). Since both pointers meet at node '0', a cycle is detected.

Common mistakes candidates make

• Null pointer exceptions: Not checking if fast or fast.next is null before moving the fast pointer two steps.
• O(n) space complexity: Using a Hash Set to store visited nodes when the interviewer specifically asks for a constant space solution.
• Initial pointer positions: Starting the pointers incorrectly, which might lead to the loop never starting or terminating prematurely.

Interview preparation tip

Always master Floyd's Cycle-Finding algorithm. It's a versatile pattern that can be used in many other problems, such as finding the duplicate number in an array or finding the starting node of a cycle.