Familiar Ground

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L3

Problem

A linked list is stored compactly as an array where next_pointers[i] holds the index of node i's successor, or -1 when node i is the tail. Starting at index 0 and following these pointers, return whether the walk ever returns to a node it already visited instead of terminating. A pointer that lands outside the array counts as a terminating tail, the same as -1.

Keep walking. Sooner or later you may recognize where you're standing.

Example 1

Input:

next_pointers = [1,2,0]

Output:

true

Example 2

Input:

next_pointers = [1,-1]

Output:

false

Worked solution and explanation

What this really is

Strip off the linked-list costume and this is a 'does a forced walk repeat itself' question. Every node has exactly one outgoing edge, its next pointer, so the path from index 0 is deterministic: there are no branches to explore and no choices to make. That single-successor property is the whole trick. A walk down a chain like this has only two possible endings: it hits a dead end (a -1 or an index past the array), or it loops forever. There is no third outcome. Candidates who reach for a general graph traversal here are overbuilding a straight-line chase.

Walking the chain

Step 1: Follow the forced path from node 0

Set current = 0. Each step, the next index to visit is simply next_pointers[current]. There is nothing to choose because each node points to exactly one place.

Step 2: Remember where you have been

Before stepping onto an index, check whether you have stood on it before. A repeat is the definition of a cycle here, so return True the moment you see one.

Step 3: Treat every off-the-end value as the tail

Both -1 and any index >= len(next_pointers) mean the chain ended. The clean way to cover both is a single bounds check 0 <= current < len(next_pointers) as the loop condition, since -1 fails the lower bound automatically.

The solution

Visited-set traversal
def has_linked_list_cycle(next_pointers: list[int]) -> bool:
    visited = set()
    current = 0
    while 0 <= current < len(next_pointers):
        if current in visited:
            return True
        visited.add(current)
        current = next_pointers[current]
    return False

The single bounds check folds the -1 tail and the out-of-range tail into one condition.

Visited set (shown above)
O(n) time, O(n) space. Easy to read, hard to get wrong, and the natural first answer. Perfectly acceptable in an interview.
Floyd's tortoise and hare
O(n) time, O(1) space. Advance a slow pointer one step and a fast pointer two steps; if they ever coincide there is a cycle. Same complexity in time, but no auxiliary memory. Mentioning it unprompted is the senior signal.

Common follow-up questions