Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Linked List

Detect a Cycle in a Linked List

Easy · Linked List · Asked at Amazon, Microsoft, Google, Goldman Sachs, TCS

The list is built from the values, and then the last node is linked back to the node at index pos (0-based). If pos = -1, there is no cycle. Print YES if the list has a cycle, otherwise NO. Solve it with O(1) extra memory.

Input

First line: n pos. Second line: the n node values.

Output

YES or NO.

Constraints

Floyd's slow and fast pointers: if they ever meet, there is a cycle.

Example 1

Input

4 1
3 2 0 -4

Output

YES

Example 2

Input

1 -1
1

Output

NO

Hints

  1. Build the list, then link the tail to node pos (if pos ≥ 0).
  2. Move slow one step and fast two steps. If fast reaches null there is no cycle; if they meet, there is one.

Approach

Floyd's cycle detection. Inside a cycle, the fast pointer gains one node per step on the slow pointer, so it must catch it; without a cycle, fast falls off the end. Only two pointers are used — no visited set.

Complexity: O(n) time · O(1) extra space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long val;
    Node *next = nullptr;
    Node(long long v) : val(v) {}
};

int main() {
    int n, pos;
    cin >> n >> pos;
    vector<Node *> nodes(n);
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        nodes[i] = new Node(x);
        if (i) nodes[i - 1]->next = nodes[i];
    }
    if (pos >= 0) nodes[n - 1]->next = nodes[pos];
    Node *slow = nodes[0], *fast = nodes[0];
    bool cycle = false;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            cycle = true;
            break;
        }
    }
    cout << (cycle ? "YES" : "NO") << "\n";
    return 0;
}

Python solution

import sys


class Node:
    def __init__(self, val):
        self.val, self.next = val, None


data = list(map(int, sys.stdin.read().split()))
n, pos = data[0], data[1]
nodes = [Node(v) for v in data[2 : 2 + n]]
for i in range(n - 1):
    nodes[i].next = nodes[i + 1]
if pos >= 0:
    nodes[-1].next = nodes[pos]
slow = fast = nodes[0]
cycle = False
while fast and fast.next:
    slow, fast = slow.next, fast.next.next
    if slow is fast:
        cycle = True
        break
print("YES" if cycle else "NO")

Java solution

import java.util.*;

public class Main {
    static class Node {
        long val;
        Node next;
        Node(long v) { val = v; }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), pos = sc.nextInt();
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(sc.nextLong());
            if (i > 0) nodes[i - 1].next = nodes[i];
        }
        if (pos >= 0) nodes[n - 1].next = nodes[pos];
        Node slow = nodes[0], fast = nodes[0];
        boolean cycle = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                cycle = true;
                break;
            }
        }
        System.out.println(cycle ? "YES" : "NO");
    }
}

Solve Detect a Cycle in a Linked List online · All practice problems