Getting everything ready for you…

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

0s

Practice › Linked List

Starting Point of a Loop

Medium · Linked List · Asked at Amazon, Microsoft, Google, Qualcomm

The list is built like in "Detect a Cycle": the last node links back to index pos (or nowhere if pos = -1). Print the index of the node where the cycle begins, or -1 if there is no cycle. Values can repeat, so find the node itself — not a value.

Input

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

Output

The 0-based index of the first node of the cycle, or -1.

Constraints

After slow and fast meet, move one pointer back to the head; advancing both one step at a time, they meet at the start of the cycle.

Example 1

Input

4 1
3 2 0 -4

Output

1

Example 2

Input

2 -1
1 2

Output

-1

Hints

  1. First detect the cycle with slow/fast pointers.
  2. Then put one pointer back at the head and move both one step at a time — they meet exactly at the first node of the cycle.

Approach

Let the head-to-cycle distance be a and the cycle length c. When slow and fast meet, slow has walked a + b and fast 2(a + b), so a + b is a multiple of c — meaning a more steps from the meeting point lands on the cycle start. Resetting one pointer to the head and stepping both by one makes them meet there. To print the index, keep a map from node to index (or walk from the head counting).

Complexity: O(n) time · O(1) extra space for the algorithm

Solution

C++ solution

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

struct Node {
    long long val;
    Node *next = nullptr;
    int idx;
    Node(long long v, int i) : val(v), idx(i) {}
};

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, i);
        if (i) nodes[i - 1]->next = nodes[i];
    }
    if (pos >= 0) nodes[n - 1]->next = nodes[pos];
    Node *slow = nodes[0], *fast = nodes[0];
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = nodes[0];
            while (slow != fast) slow = slow->next, fast = fast->next;
            cout << slow->idx << "\n";
            return 0;
        }
    }
    cout << -1 << "\n";
    return 0;
}

Python solution

import sys


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


data = list(map(int, sys.stdin.read().split()))
n, pos = data[0], data[1]
nodes = [Node(v, i) for i, v in enumerate(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]
ans = -1
while fast and fast.next:
    slow, fast = slow.next, fast.next.next
    if slow is fast:
        slow = nodes[0]
        while slow is not fast:
            slow, fast = slow.next, fast.next
        ans = slow.idx
        break
print(ans)

Java solution

import java.util.*;

public class Main {
    static class Node {
        long val;
        int idx;
        Node next;
        Node(long v, int i) { val = v; idx = i; }
    }

    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(), i);
            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];
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                slow = nodes[0];
                while (slow != fast) { slow = slow.next; fast = fast.next; }
                System.out.println(slow.idx);
                return;
            }
        }
        System.out.println(-1);
    }
}

Solve Starting Point of a Loop online · All practice problems