Linked list: how to spot it
We'll cover the following
Nodes link to the next node instead of sitting in an array. Almost every problem is about moving pointers and rewiring arrows without losing the rest of the list.
How the question sounds
- Reverse, merge, or reorder a list in place
- Cycle detection or finding the start of a cycle
- Find the middle or the nth node from the end
- Use a dummy head node to avoid special cases
- LRU cache: a hash map plus a doubly linked list
The two shapes
Where it shows up in GenAI work
An LRU cache for prompts, embeddings or KV state is a hash map plus a doubly linked list. Streaming pipelines and token buffers are linked structures, and fast and slow pointers show up when you reason about loops in agent workflows.
Is it linked list?
Decide yes or no before you open each answer.
Check yourselfReverse a linked list in place.
Yes. Rewire each arrow with prev, cur and next.
Check yourselfDetect whether a linked list has a cycle.
Yes. Fast and slow pointers meet inside a cycle.
Check yourselfDesign an LRU cache with O(1) get and put.
Yes. A hash map for lookup plus a doubly linked list for recency order.
Check yourselfFind two numbers in a sorted array that sum to a target.
No. An array with two pointers from both ends.
Check yourselfReturn the k most frequent words.
No. Count with a hash map, then use a heap.
Check yourselfCount the islands in a grid.
No. A grid search, so BFS or DFS.
Problems in this pattern
- Reverse a linked list · Easy · Pointer rewiring
- Detect a cycle · Medium · Slow and fast
- Merge two sorted lists · Easy · Two heads
- Remove nth node from the end · Medium · Gap pointers
Summary: say it in the interview
- Rewiring: Save next before you change an arrow, or you lose the rest of the list.
- Fast and slow: Two pointers at different speeds find the middle, a cycle, or the nth node from the end in one pass.