Linked List Cycle

easyFREELinked ListBlind 75

Given a list of values and an integer pos indicating where the tail connects to (0-indexed), determine if the linked list has a cycle.

pos is -1 if there is no cycle. Output True if there is a cycle, False otherwise.

Example

Input

3,2,0,-4
1

Output

True

Reasoning

The first input line is the node values in order, so the list is $3 \to 2 \to 0 \to -4$ (nodes at indices 0, 1, 2, 3).
The second line is pos = 1: the tail node ( $-4$ , index 3) does not end the list but links back to the node at index 1, whose value is $2$ .
Walking the links from the head visits $3, 2, 0, -4, 2, 0, -4, 2, \dots$ : after the first node, the three nodes $2, 0, -4$ repeat forever and the walk never reaches an end.
A walk that never ends is exactly what a cycle means, so the output is True.
Notice the loop holds the nodes from index 1 up to the tail at index 3, which is $4 - 1 = 3$ nodes, and the node with value $2$ is the first one the walk sees twice, right after the tail $-4$ . If the tail linked to nothing, the walk would simply stop after the 4th node ( $-4$ ).

Constraints

0 <= number of nodes <= 10^4
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The Linked List data structure is a fundamental concept in computer science, consisting of nodes that contain a value and a reference (i.e., a "link") to the next node in the sequence. In the context of this problem, we're dealing with a singly linked list, where each node only points to the next node. A cycle in a linked list occurs when a node points back to a previous node, creating a loop.

To understand the problem, it's essential to be familiar with traversal algorithms, which are used to visit each node in the linked list. The two primary traversal techniques are iterative and recursive. In this case, an iterative approach is likely more suitable. Additionally, understanding the concept of pointers or references is crucial, as they are used to connect nodes in the linked list.

The problem also involves graph theory, specifically the concept of a cycle detection. In graph theory, a cycle is a path that starts and ends at the same node, passing through at least one edge more than once. In the context of linked lists, cycle detection can be achieved using various algorithms, including the Floyd's Tortoise and Hare algorithm, also known as the slow and fast pointers technique.

Algorithm/Approach

The general approach to solving this problem involves using a cycle detection algorithm to determine if the linked list has a cycle. One common algorithm pattern used to solve this type of problem is the Floyd's Tortoise and Hare algorithm, which utilizes two pointers that move at different speeds through the linked list. If a cycle exists, these two pointers will eventually meet at some node within the cycle.

Step-by-Step Strategy

To implement the solution, follow these steps:

Create a function that takes the head of the linked list as input.
Initialize two pointers, slow and fast, to the head of the linked list.
Traverse the linked list using a loop, moving the slow pointer one step at a time and the fast pointer two steps at a time.
Check if the fast pointer reaches the end of the linked list (i.e., None) or if the slow and fast pointers meet at some node.
If the fast pointer reaches the end, return False, indicating no cycle. If the slow and fast pointers meet, return True, indicating a cycle.

Common Pitfalls

When implementing the solution, watch out for the following:

Ensure that the fast pointer is checked for None before accessing its next attribute to avoid a NoneType error.
Be careful when initializing the slow and fast pointers to avoid pointing to the wrong node.
Consider edge cases, such as an empty linked list or a linked list with only one node.

Time & Space Complexity

The expected time complexity for this problem is $O(n)$ , where $n$ is the number of nodes in the linked list, since we only traverse the list once. The space complexity is $O(1)$ , as we only use a constant amount of space to store the slow and fast pointers.

solution.py

Python 3.13

Test results