Linked List Cycle Detection

Determine whether a singly-linked list loops back on itself instead of ending in null.

Given the head of a singly-linked list, determine whether the list contains a cycle -- that is, whether following next pointers from some node eventually leads back to a node you've already visited, rather than reaching the end of the list.

To describe a list that may contain a cycle, each test case is given as the list's node values plus an integer pos, where pos is the zero-indexed position of the node that the last node's next pointer connects back to. If pos is -1, there is no cycle and the last node's next pointer is null as usual. Note that pos only describes the shape of the input list for you to reason about -- it is not passed to your function as an extra value to inspect.

Return true if the list has a cycle, or false otherwise.

Example 1

Input: head = [3,2,0,-4], pos = 1

Output: true

Explanation: The last node (-4) connects back to the node at index 1 (value 2), forming a cycle.

Example 2

Input: head = [1,2], pos = 0

Output: true

Explanation: The last node connects back to the first node.

Example 3

Input: head = [1], pos = -1

Output: false

Explanation: The single node's next pointer is null, so there is no cycle.

Constraints

The number of nodes in the list is in the range [0, 10000].
-100000 <= Node.val <= 100000
pos is -1 or a valid index into the list of values.

Follow-up

Can you solve it using O(1) extra memory, without storing visited nodes?

Hints

Companies

No companies reported yet.

Discussion

Loading discussion...

class Solution {
    public boolean hasCycle(ListNode head, int pos) {
        // your code here
        return false;
    }
}

Test results

No test cases yet.