On an even-length linked list, which of the two middle nodes does a fast/slow walk land on?

### There are two middles, and the code has to choose For an odd count there is a unique middle: on a five-record capture chain, record 3 has two records on each side. For an even count there is no such record. A four-record chain has records 2 and 3 with equal claim, and any implementation silently commits to one of them. The interview question is not *what is the middle* but *which one does your loop return, and why*. ### The choice lives in the initialisation Both variants run the identical loop — advance slow one link, fast two, guarded so fast never reads past the end. The only difference is where fast begins. **Variant A, fast starts at the head.** Trace a four-record chain (records 1..4). Start slow = 1, fast = 1. Iteration one: fast has a link and a link beyond it, so slow = 2 and fast = 3. Iteration two: record 3 has a link to 4, so slow = 3 and fast becomes nothing (two hops from record 3 falls off the end). The guard now fails and the walk returns record 3 — the **second** middle. **Variant B, fast starts one node ahead.** Start slow = 1, fast = 2. Iteration one: record 2 has a link to 3, so slow = 2 and fast = 4. Now record 4 has no link, the guard fails, and the walk returns record 2 — the **first** middle. ### The full landing table | records | fast starts at head | fast starts one ahead | |---|---|---| | 1 | record 1 | record 1 | | 2 | record 2 | record 1 | | 3 | record 2 | record 2 | | 4 | record 3 | record 2 | | 5 | record 3 | record 3 | | 6 | record 4 | record 3 | In closed form, variant A lands on `floor(n/2) + 1` and variant B lands on `ceil(n/2)`, counting records from one. The two columns are identical on every odd row and differ by exactly one node on every even row. That is the single most useful fact in this whole area: **a suite made only of odd-length cases cannot tell the two conventions apart**, so an off-by-one in the convention survives it untouched. ### Why a two-record chain is the test to write first It is the smallest input where the columns disagree. Variant A returns the second record; variant B returns the first. An empty or one-record chain only exercises the guard, and every odd length agrees. If someone hands you a middle-finding routine and asks which convention it implements, feed it two records and you have the answer in one step — no tracing required. ### The initialisation has a boundary cost Variant B reads the head's link before the loop begins. On an empty chain there is no head to read from, so that variant needs an explicit check before initialisation. Variant A has no such problem: its loop guard tests the fast reference itself first, so an empty chain simply skips the body. This is a real, if small, argument for variant A as the default — it has one fewer special case. ### Why it matters beyond pedantry Callers build on the answer. A routine documented as *returns the middle* that quietly returns the later middle on even counts will disagree with a second routine written by someone who assumed the earlier one, and the disagreement only shows up on even-length inputs — often in production, on the one chain length nobody tested. The fix is not cleverness; it is naming the convention in the contract (*returns the first of the two middle records when the count is even*) and pinning it with a two-record test. ### Getting the other middle for free If you already run variant A but want the earlier middle, you do not have to restructure the loop. Keep a reference trailing slow by one node, updated just before each advance. When the loop exits, slow is on `floor(n/2) + 1` and the trailing reference is on `ceil(n/2)` — both middles in the same sweep and still constant space. That is usually a better answer in an interview than swapping the initialisation, because it shows you understand the offset instead of memorising two templates. ### The wrong answer to avoid The weak response is *the middle is the middle*, followed by hand-waving when asked about four records. The strong response names the landing node exactly, explains that the initialisation and not the loop decides it, and offers the two-record case as proof before the interviewer asks for one.