Linked List Cycle

Q: What is the time and space complexity of Linked List Cycle?

Both approaches take O(n) time, since every node is passed a bounded number of times. Marking visited nodes needs O(n) extra memory. Floyd's fast and slow pointers need O(1) : two node numbers.

Q: Why can't the fast pointer skip over the slow pointer?

Inside the cycle, each round fast moves two nodes and slow one, so the distance fast must still cover to reach slow drops by exactly one. A distance that drops by one per round goes 3, 2, 1, 0 and cannot pass zero, so the two pointers meet on a node.

Q: Can you detect the cycle by counting steps?

In this array form, yes: a list without a cycle reaches -1 within n links, so walking n links without reaching the end proves a cycle, in O(1) memory. It needs the number of nodes, which a list made of pointers does not give you, and counting them first never finishes when there is a cycle. Floyd's method needs no count.

EasyFast and slow pointers Linked list

+10

A linked list is stored in the array next: node i links to node next[i], and -1 means the list ends there. The head is node 0. Follow the links from the head and return true if you ever come back to a node you have already visited, or false if you reach the end. Nodes the walk never reaches do not count, even if they link to each other in a loop.

Function

hasCycle(next: integer-array) → boolean

nextinteger-array: the link of every node: next[i] is the node after node i, or -1
Returnsboolean: true if the walk from node 0 revisits a node, false if it reaches -1

Constraints

1 ≤ next.length ≤ 10⁴
-1 ≤ next[i] ≤ next.length-1
Several nodes may link to the same node, and some nodes may be unreachable from the head.

Examples

Input: next = [1, 2, 3, 1]
Output: true
Explanation: The walk goes 0, 1, 2, 3 and then back to 1. Node 1 is visited twice, so the list has a cycle through nodes 1, 2 and 3.

Input: next = [2, -1, 1]
Output: false
Explanation: The walk goes 0, 2, 1 and then reaches -1: three different nodes and then the end, so there is no cycle.

Input: next = [-1, 2, 1]
Output: false
Explanation: Node 0 links to -1, so the list is one node long. Nodes 1 and 2 link to each other in a loop, but the walk from the head never reaches them.

+16 hidden tests on Submit

Follow-up

Can you also find the node where the cycle begins, still with O(1) extra memory?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A list without a cycle reaches -1 within n links, but a list with a cycle never ends, so you cannot wait for the end. You need a way to notice that the walk is going around. Remembering every node you visit does it with O(n) memory. Floyd's fast and slow pointers do it with two integers, because a pointer moving twice as fast must catch up with the slow one inside a loop.

Mark the nodes you visit

Intuition

Walk from node 0 and mark each node as you leave it. If you arrive at a node that is already marked, the walk has come back to it, and from there it repeats forever: that is a cycle. In example 1 you mark 0, 1, 2 and 3, and the link from node 3 leads to node 1, which is marked.

Nodes are numbered 0 to n-1, so a boolean array of length n serves as the set of visited nodes. In a linked list built from objects you would put the node references in a hash set instead; the idea is the same.

Each node is marked at most once, and the walk stops at the first repeat or at -1, so it takes at most n steps: O(n) time and O(n) memory for the marks.

Algorithm

Create a boolean array visited of length n, all false.
Set node = 0.
While node is not -1, return true if visited[node] is already true.
Otherwise set visited[node] and move to next[node].
When the walk reaches -1, return false.

def hasCycle(next):
    visited = [False] * len(next)
    node = 0
    while node != -1:
        if visited[node]:
            return True  # back at a node already on the path
        visited[node] = True
        node = next[node]
    return False

Fast and slow pointers (Floyd's cycle detection)

Intuition

Start two pointers at the head. slow follows one link per round and fast follows two. If the list ends, fast reaches -1 first and you return false. If there is a cycle, fast enters it first and keeps circling until slow arrives too.

Once both are in the cycle, every round fast gains exactly one node on slow. The distance fast still has to cover to reach slow drops by one each round, so it reaches zero and the pointers land on the same node. Gaining one node at a time, fast can never jump over slow.

In example 1, after one round slow is on node 1 and fast on node 2. After two rounds slow is on 2 and fast has gone 3, 1. After three rounds both are on node 3, so the answer is true.

slow needs at most n rounds to enter the cycle, and once it is inside they meet before it finishes one lap, so the time is O(n). The only memory is two node numbers.

Algorithm

Set slow = 0 and fast = 0.
While fast is not -1 and next[fast] is not -1, move slow one link and fast two links.
After each move, return true if they are on the same node.
When the loop stops, fast found the end: return false.

def hasCycle(next):
    slow = 0
    fast = 0
    # fast needs two links to move; if either is missing, the list ends.
    while fast != -1 and next[fast] != -1:
        slow = next[slow]
        fast = next[next[fast]]
        if slow == fast:
            return True
    return False

Pitfalls and edge cases

The bugs here are about the end of the list and about which nodes count.

Moving fast two links without checking both. fast and next[fast] must both be real nodes before you read next[next[fast]]; otherwise you read next[-1], which crashes in most languages and quietly returns the last element in Python.
Comparing the pointers before moving them. Both start at node 0, so a check at the top of the loop reports a cycle in every list.
Looking at the whole array instead of the walk. In [-1, 2, 1] nodes 1 and 2 form a loop, but the head ends right away, so the answer is false. Checking whether a value repeats in next is also wrong: in [4, 4, 4, 4, -1] several nodes link to node 4 and there is no cycle.
Assuming a cycle must lead back to the head. In [1, 2, 3, 4, 4] the last node links to itself, and in [0] the head does.

Frequently asked questions4

How does Floyd's cycle detection work?

Two pointers start at the head: one moves one link per step, the other two. Without a cycle the fast one reaches the end. With a cycle both end up inside it, the fast one closes the gap by one node per step, and they meet on the same node.

What is the time and space complexity of Linked List Cycle?

Both approaches take O(n) time, since every node is passed a bounded number of times. Marking visited nodes needs O(n) extra memory. Floyd's fast and slow pointers need O(1): two node numbers.

Why can't the fast pointer skip over the slow pointer?

Inside the cycle, each round fast moves two nodes and slow one, so the distance fast must still cover to reach slow drops by exactly one. A distance that drops by one per round goes 3, 2, 1, 0 and cannot pass zero, so the two pointers meet on a node.

Can you detect the cycle by counting steps?

In this array form, yes: a list without a cycle reaches -1 within n links, so walking n links without reaching the end proves a cycle, in O(1) memory. It needs the number of nodes, which a list made of pointers does not give you, and counting them first never finishes when there is a cycle. Floyd's method needs no count.

Python

def hasCycle(next):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

next = [1, 2, 3, 1]

Expected

true