Linked-List Intersection With Cycles

Given two singly-linked lists that may each contain a cycle, determine whether they share any node. The intersection (if any) can be a shared chain or a shared cycle. Requirements Input: two ListNode heads, each list may or may not contain a cycle. Output: boolean — True if the two lists share at least one node, False otherwise. Optional: return the first shared node when the answer is True. Notes The cycle-free case is the canonical "two-pointer length-difference" trick: walk to each tail measuring length, then advance the longer head by the difference, then walk in lockstep; the first equal pointer is the intersection. With cycles, first detect each list's cycle with Floyd's algorithm. Cases: Neither cycles → linear intersection check (above). Exactly one cycles → no intersection (a cycle cannot end, and the other list terminates at null). Both cycle → check whether the two cycles are the same cycle: pick any node A on list 1's cycle; walk list 2's cycle for at most one loop; if A is encountered, they share the cycle; otherwise they do not. If they share the cycle, the first intersection is at the join point (or earlier if a tail merges in). Hashmap fallback (O(n + m) space): traverse list 1 inserting every node id into a set; traverse list 2 checking membership. Acceptable for the warmup, but the interviewer will push for O(1) space. Edge cases: one or both lists empty, single-node list, lists that share head, two lists that are the same cycle but start at different "entry tails". The interviewer does not volunteer whether each list contains a cycle — you must ask. Assuming "no cycle" because the prompt looks like the classic intersection problem is a setup to fail; this is deliberately not a LeetCode-original framing. The follow-up asks you to return the shared node (not just a boolean), which expands the case analysis to roughly five sub-cases: neither cycles; exactly one cycles; both cycle on disjoint cycles; both share the same cycle but enter at different points; both share a common tail that merges into one cycle. Be ready to enumerate and handle each. The 45-minute slot is tight: writing the solution, hand-building test cases, and handling the return-node follow-up rarely all fit. Interviewers may not have ready-made test inputs (their reference tests are sometimes in another language), so expect to construct linked nodes by hand to demonstrate correctness. Preparation Implement Floyd's cycle detection cold; identify both the meeting point and the cycle entry. Write the cycle-free intersection in under 10 minutes; layer the cycle-handling on top. Hand-trace a Y-shaped example (two tails merging into a shared chain) and a pq-shaped example (one tail merging into the middle of a cycle). Pre-write a one-sentence answer for "what if both lists could be infinite generators rather than fixed linked lists?" (the answer flips to streaming + bloom-filter dedup).