Question 1

How do you check whether a linked list has a cycle?

Accepted Answer

Answer this with two solutions — one solution reads as average, comparing two reads as good. Solution 1 — hash set: add visited nodes to a Set; hitting one you've seen means a cycle. O(n) time, O(n) memory. Its virtues: five lines, hard to get wrong, and it gives the cycle's start directly. Solution 2 — Floyd (tortoise and hare): slow moves one step, fast two; if they meet there is a cycle, if fast hits null there isn't. O(n) time, O(1) memory. Why Floyd works — explaining this is the core of the answer: "Once both are inside the loop the gap shrinks by exactly 1 each step, because fast moves 2 and slow moves 1. A decreasing integer must reach 0 — so they meet without jumping over each other." A code detail: while (fast != null && fast.next != null) — without that guard fast.next.next blows up on null. It's the most frequently caught mistake. The choice: "With no memory constraint stated I'd start with the hash set because it's simple and readable. If memory is critical or the interviewer wants O(1), I switch to Floyd." That sentence shows practical judgement — readability is a criterion in real code too. Be ready for the follow-up: "where does the cycle start?" nearly always comes next.

Question 2

How do you find the node where the cycle starts, and why does that method work?

Accepted Answer

The algorithm: after the pointers meet, send one back to the head, keep the other at the meeting point, and move both one step at a time. The node where they meet is the start of the cycle. Why it works — this part is what distinguishes the answer. Name the distances: a = head to entrance, b = entrance to meeting point, c = meeting point back to entrance. The loop length is b + c. Slow has taken a + b steps; fast twice as many, having lapped k times: a + b + k(b + c) = 2(a + b). Hence a = (k−1)(b + c) + c. So a equals c up to whole laps — walking from the head to the entrance takes the same number of steps as walking from the meeting point to the entrance. That's why two pointers at equal speed meet exactly at the entrance. Interview tactic: you don't need to write the full derivation, and doing so risks burning time. "The arithmetic works out so that a equals c, which is why it works" is enough; if the interviewer wants depth, expand it on the board. What matters is presenting it as a reasoned result rather than a memorised trick. The simple alternative: with the hash set approach, the first repeated node you see is already the cycle's start — no maths needed, at the cost of O(n) memory. Mentioning it signals "I don't always reach for the cleverest solution".

Question 3

What is the connection between the "happy number" problem and linked-list cycle detection?

Accepted Answer

This question tests whether you can think one level of abstraction up — that is where the value of the answer lies. The connection: Floyd's algorithm is not really about linked lists. All it needs is a function giving exactly one next state from each state. In a linked list that function is node.next. In happy number it is "the sum of the squares of the digits": 19 → 82 → 68 → 100 → 1. So each number is a node and next(x) plays the role of the pointer. The sequence either reaches 1 (a happy number) or falls into a repeating cycle (not happy). There is no third option, because the values are bounded. The code is practically identical: slow = next(slow), fast = next(next(fast)), until fast == 1 or slow == fast. The generalisation — this sentence strengthens the answer: "This pattern is called a functional graph — every node has exactly one outgoing edge. Such a graph is always shaped like a tail plus a loop. That's why Floyd works for all of these: happy numbers, repeating pseudo-random sequences, and finding a duplicate in an array via the mapping nums[i] → i." That last example is especially valuable: given n+1 numbers in the range 1..n, find the duplicate — without mutating the array and in O(1) memory. The mapping i → nums[i] forms a functional graph, and the duplicate is precisely the start of the cycle. Being able to draw that link is an above-middle signal. Name the alternative too: keeping seen values in a hash set gives the same result with O(n) memory — simple and readable.

Question 4

How do you find the middle of a linked list in one pass? How does it differ from the two-pass solution?

Accepted Answer

The two-pass solution: walk the list to count the length (n), then start again and take n/2 steps. Simple and correct: O(n) time, O(1) memory. The one-pass solution: slow moves one step, fast two. When fast reaches the end, slow is at the middle — because fast is twice as fast. Again O(n) time, O(1) memory. So what's the difference? — that is the real point of the question, and answer it honestly: asymptotically there is none. Both are O(n). The one-pass version traverses the list once instead of twice — a constant factor of two, with identical Big O. When does it genuinely matter then? Three cases: The data is a stream — you cannot read it a second time; a single pass is mandatory The list is very long and cache behaviour matters — two passes mean twice the memory traffic The length isn't known and computing it is expensive An important detail — even length: on a four-node list, is the "middle" the 2nd or the 3rd? The standard template returns the second. For the first you change the loop condition. In an interview you should ask: "which middle do you want on an even length?" That question signals care, and most candidates don't ask it. Practical use: this technique is the first step of merge-sorting a linked list and of the "is it a palindrome" problem — find the middle, then reverse the second half. Noting that link shows the technique isn't an isolated trick.

Question 5

How do you apply two pointers to find the k-th node from the end?

Accepted Answer

The idea: keep a fixed gap of k between two pointers. Advance the first k steps, then move both together. When the first reaches the end, the second is on the k-th node from the end. Why it works: the gap never changes. If the first is at position n, the second is at n − k. This is the "different offset" variant of fast/slow rather than the "different speed" one — the second member of the same family. Complexity: O(n) time, O(1) memory, one pass. Edge cases — list them out loud, because they are why the question is asked: k larger than the list length? Advancing the first pointer hits null — return null or throw, and settle the behaviour with the interviewer k == n (the first element) — this bites especially in the deletion variant, since you'd have to remove the head itself k == 0 or negative — validate the input The most common follow-up: "delete the k-th node from the end." There is a subtlety: to delete, you must reach the node before the one being removed, so you keep the pointer one step behind. The practical trick is a dummy head: dummy.next = head. That turns "delete the first element" from a special case into an ordinary one and cuts five lines of code. Knowing the dummy-head technique is a serious advantage on linked-list problems and gets noticed in interviews. The two-pass alternative: count the length, then take n − k steps. Same complexity, two passes — and it doesn't work on streamed data.

Problem	How it applies	Memory
Does the linked list have a cycle?	slow by 1, fast by 2; if they meet there is a cycle	O(1)
Where does the cycle start?	After meeting, send one back to the head and move both by 1	O(1)
Middle of the list (one pass)	when fast reaches the end, slow is in the middle	O(1)
The k-th node from the end	Advance one pointer k steps first, then move both together	O(1)
Happy-number style problems	A "next value" function forms an implicit linked list; a cycle means not happy	O(1)
Find the duplicate number in an array (1..n)	The mapping `i → a[i]` forms a graph; the duplicate is the cycle's start	O(1) — without mutating the array
Is the linked list a palindrome?	Find the middle, reverse the second half, compare	O(1)

Fast/slow pointers and cycle detection