You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:
A large-scale backend system processes streams of events using linked lists to represent execution flows, job pipelines, or dependency chains. Due to misconfiguration, bugs, or pointer mismanagement, a linked list may accidentally form a cycle, causing infinite loops, memory leaks, or system hangs.
Before executing or processing the list further, the platform must detect whether a cycle exists in the linked structure.
Each node in the list contains a value and a reference to the next node.
This is a common practice coding problem for DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.
Your Task
Given the head of a singly linked list, determine if the linked list contains a cycle.
A cycle exists if a node can be reached again by continuously following the next pointers.
Return true if there is a cycle, otherwise return false.
Input Format
head: the head node of a singly linked list
Each node is defined as:
ListNode { int val; ListNode next; }
Output Format
- A boolean value
true if the linked list contains a cyclefalse otherwise
Examples
Example 1:
Input: head = [3,2,0,-4]
pos = 1
Output: true
Explanation: The tail connects to the node at index 1, forming a cycle.
Example 2:
Input: head = [1,2]
pos = 0
Output: true
Example 3:
Input: head = [1]
pos = -1
Output: false