Frontend School

Detect Cycle in Linked List

DSA
easy

Detect Cycle in Linked List

Easy
Linked List
Two Pointers

Overview

At Pinterest, user interactions and content relationships can often be modeled as sequences, sometimes represented by linked lists. Maintaining the integrity of these sequences is vital for features like recommendation feeds or content moderation queues. An unexpected cycle in such a sequence could lead to infinite loops, performance degradation, or incorrect data processing. This problem asks you to identify such a structural anomaly.

What you need to do / Task

You are given the head of a singly linked list. Your task is to implement a function that determines whether a cycle exists in the linked list. A cycle exists in a linked list if some node in the list can be reached again by continuously following the next pointer.

Return true if there is a cycle in the list, or false otherwise.

Input & output

The function hasCycle takes one parameter:

  • head: The head node of a singly linked list. It can be null if the list is empty.

The function should return:

  • true if a cycle is detected in the linked list.
  • false if no cycle is detected.

Clarifications

  • Empty List: If head is null, the list is empty and cannot have a cycle.
  • Single Node List: A list with a single node can have a cycle if its next pointer points back to itself.
  • Definition of Cycle: A cycle means that by traversing next pointers, you will eventually revisit a node you've already seen.

Examples

1

Example 1

Input:

head = [3,2,0,-4]

Output:

true

Note:

The last node, with value -4, connects to the node with value 2, forming a cycle.

2

Example 2

Input:

head = [1,2]

Output:

true

Note:

The last node, with value 2, connects to the node with value 1, forming a cycle.

3

Example 3

Input:

head = [1]

Output:

false

Note:

The list has only one node, and its next pointer is null, so there is no cycle.

Constraints

Constraints & assumptions

  • The number of nodes in the list is in the range [0, 10^4].
  • -10^5 <= Node.val <= 10^5
  • pos is used in the test cases to denote the index of the node that the last node's next pointer connects to. If pos is -1, there is no cycle. You should not rely on pos in your solution logic; your function only receives head.

What interviewers evaluate

  • Correctness: The solution must correctly identify cycles in all valid test cases, including edge cases.
  • Efficiency: The solution should aim for optimal time and space complexity (ideally O(N) time and O(1) space).
  • Code Quality: Readability, maintainability, and proper use of data structures and algorithms.
  • Problem-Solving: Ability to break down the problem and apply appropriate algorithmic techniques.

Loading editor...