Interactive Lab · DSA & Algorithms

Three pointers to reverse it, two runners to catch a loop, the linked list

A singly linked list is just nodes that each know one thing: who comes next. No indices, no going back. That's why the two interview classics are all about pointer discipline. Reverse it in place: walk with prev, cur and nxt, and flip one arrow per step, but save cur.next before you overwrite it or the rest of the list is gone. Detect a cycle: send a slow tortoise (1 step) and a fast hare (2 steps). If there's a loop, the hare laps the tortoise and they must meet, using O(1) memory. Step through both below.

▶ The playground, pick a problem, then step the pointers

list length 7

310

tail links back to node 2

no cyclelast node

step 0 / 0

🧭 Where this fits

Linked lists are the warm-up round at almost every Indian product-company and service-company interview (reverse a list, detect a loop, find the middle, merge two sorted lists), because they test whether you can manage pointers without losing data. The same ideas run real systems: an LRU cache is a hash map plus a doubly linked list, the Linux kernel's scheduler queues are intrusive linked lists, and Floyd's tortoise-and-hare finds cycles in anything with a "next" function, from detecting a duplicate in an array (LeetCode 287) to Pollard's rho factoring.

The code that's actually running, the highlighted line is the current step

🔮 Predict, then test

Switch to Floyd's cycle detection, set the length to 10 and make the tail link back to node 0 (the whole list is one loop). Predict: the hare moves twice as fast, so how many steps until it catches the tortoise, and where? Then move the cycle start to node 6 and watch phase 2: one pointer restarts from the head, both move one step at a time, and they meet exactly at the cycle's first node. Why does restarting from the head work?

The takeaway

Your new mental model of linked lists

Save before you overwrite. Reversal is three moves per node: nxt = cur.next (save the rest), cur.next = prev (flip the arrow), then shift prev, cur = cur, nxt. Skip the save and you lose every node after cur.
One pass, O(1) memory. Each node's arrow is rewritten exactly once, so reversal is O(n) time with just three pointer variables. No new list, no stack.
Fast and slow pointers. The hare gains one node per step on the tortoise. Once both are inside the loop, the gap shrinks by one every step, so they must meet, within one lap. No cycle means the hare simply hits None.
Finding the cycle start. If the tail is μ nodes long, the meeting point is exactly μ steps (mod the loop length) before the start. So a pointer from the head and a pointer from the meeting point, both stepping by one, arrive at the cycle start together.
Why not a hash set? Storing every visited node also finds the cycle, but costs O(n) memory. Interviewers want the O(1) answer, and the same two-speed trick finds the middle of a list too (when the hare reaches the end, the tortoise is halfway).

← Two Pointers Placement prep →Try: Recursion