To detect the intersection node by reference when two singly linked lists have different lengths, which sequence of steps is correct?

• A. Compute the lengths of both lists, advance the longer list by the difference, then move both lists forward in lockstep until they reference the same node.
• B. Traverse both lists simultaneously from their heads and compare nodes at each step to find a match.
• C. Reverse one list and compare from the head to identify a common reference.
• D. Advance the shorter list by the sum of the lengths and compare node references.

Answer: (A)

You detect the intersection by reference by aligning the two lists so their remaining portions after alignment are equal in length. First, determine the length of each list. If one list is longer, advance its head by the difference in lengths, so both pointers have the same number of nodes left to traverse. Then move both pointers forward together, one node at a time, until they reference the same node. If such a node is found, that’s the intersection by reference; if you reach the end (null) without meeting, there is no intersection. This works because after alignment, the tails of the two lists are of equal length, so if an intersection exists, both pointers will reach it at the same time. The approach is efficient: it runs in O(m+n) time and uses O(1) extra space.

Other strategies don’t handle different lengths properly. Traversing from the heads in lockstep without accounting for the length difference can miss the intersection. Reversing one list is destructive and doesn’t reliably reveal a shared reference. Advancing the shorter list by the sum of lengths doesn’t align the pointers correctly, so it fails to identify a common intersection.