Intersection of Two Lists

Use two pointers p and q starting at the two heads. Advance each by one node; when p reaches null, redirect it to head B, and when q reaches null, redirect it to head A. If the lists intersect by node identity, the pointers meet at the first shared node after each has travelled the unique prefix of one list plus the full length of the other. If there is no intersection, both become null together. This avoids computing lengths or extra storage. The proof depends on shared tail structure: once lists intersect, all subsequent nodes are identical references. Do not compare node values, because equal values in separate nodes are not an intersection. Test an intersection at head, no intersection, one empty list, unequal prefix lengths, and a single shared final node. Each pointer traverses at most m+n nodes, so time is O(m+n) and extra space O(1). This assumes acyclic lists; cycles require separate handling.