Detect Cycle in Linked List

MediumPython00:00

Practice interviewer

Your interviewer

In session

Interviewer

Welcome to the Python screen.

The question is on your right: Detect Cycle in Linked List. Read through the requirements first.

Run and submit your code as often as you need. You also have five interviewer messages this session - want to talk through your approach, or are you ready to start coding?

You need to log in / sign up to run or submit.

Problem

At Slack, a service may receive malformed linked-list structures from an in-memory cache. Write a function that determines whether a singly linked list contains a cycle.

A cycle exists if following next pointers eventually revisits a previously seen node instead of reaching None.

Formal Specification

Implement a function that takes the head of a singly linked list and returns a boolean:

Input: head, the first node of a singly linked list, or None
Output: True if the list contains a cycle, otherwise False

Each node has:

val: integer value
next: reference to the next node or None

Constraints

0 <= number of nodes <= 10^5
-10^9 <= node.val <= 10^9
Each node has a next pointer to another node or None
The input may contain a cycle
Prefer O(1) extra space

Function Signature

def has_cycle(head):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output