# Familiar Ground > Keep walking. Sooner or later you may recognize where you're standing. Canonical URL: 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`. ## 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. > **Trick to solving** > > Remember which indices you have already stepped on. Walk from index 0, and the instant you land on an index that is already in your visited set, you have proven a loop. If you fall off the end first (`-1` or out of range), there is no cycle. --- ### 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** ```python 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.* > **Time and space** > > **Time:** O(n). Each index is added to the set at most once, so the walk takes at most n steps before it either repeats or runs off the end. > > **Space:** O(n) for the visited set. The set is what buys you the early exit; without it you could not tell a long-but-finite chain from a loop. **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 pitfall** > > Forgetting that a next pointer can point out of bounds, not just to `-1`. If you only check `current != -1`, a stray index like 5 in a length-2 array throws an IndexError instead of being treated as a tail. The `0 <= current < len(...)` guard handles both endings at once. > **Interviewers watch for** > > Whether you reach for the O(1)-space tortoise-and-hare once the set solution is on the board. The set answer is correct and they will accept it, but naming the constant-space alternative and explaining why it works is what separates a passing answer from a strong one. --- ## Common follow-up questions - Once you know a cycle exists, how would you find the index where it begins? _(Tests Floyd's phase 2: reset one pointer to the head and advance both one step at a time until they meet.)_ - Can you detect the cycle without using any extra memory proportional to the input? _(Tests whether the candidate can articulate the constant-space slow/fast pointer method.)_ - What changes if the list is made of real node objects with a `.next` reference instead of an index array? _(Tests adapting the same idea from an index array to object references, where 'out of range' becomes 'next is None'.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/familiar_ground) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.