Detect a linked list cycle and return its entry and length
An edge server follows redirect rules: /old-blog goes to /blog, which goes to /news, and so on. Each rule points to at most one next rule, so a chain of redirects is a singly linked list. A bad config can make the chain loop forever. When that happens, the dashboard must say which rule the loop starts at and how many rules are in the loop, so an engineer can fix the right one.
Implement findLoop(head). It returns null when the list ends, or { entry, length } when it loops.
findLoop(head) // => null | { entry: node, length: number }
{ value: '/old-blog', next: nodeOrNull }
head is the first node, or null for an empty list.value. Compare nodes by identity (===), never by value.next from head reaches null, return null.entry is the first node, walking from head, that belongs to the loop (the node you would visit twice first). length is the number of distinct nodes in the loop. A node whose next is itself is a loop of length 1.Set, Map, WeakSet or WeakMap; the tests make them unavailable.// /a → /b → /c → /d → /e
// ↑ │
// └───────────┘ (/e redirects back to /c)
findLoop(a); // => { entry: c, length: 3 }
// /a → /b → /c → null
findLoop(a); // => null
// /a → /a (redirects to itself)
findLoop(a); // => { entry: a, length: 1 }
findLoop(null); // => null
Walk two pointers, one twice as fast as the other. If they ever meet, there is a loop. Think about how far the meeting point is from the loop’s entry.