Intersection of Two Linked Lists

Problem Given the heads of two singly linked lists, return the node at which they intersect, or null if they do not. Intersection is by reference (the same node object), not by value. The lists must retain their original structure.

Input / Output

• Input: heads A and B of two singly linked lists.
• Output: the intersecting node, or null.

Constraints

• Lengths up to 3 * 10^4; aim for O(m+n) time and O(1) extra space.

Example

• A = 4→1→8→4→5, B = 5→6→1→8→4→5 (sharing the node 8) → node 8.

Expected approach

• Two pointers: walk a from headA and b from headB; when a pointer reaches the end, redirect it to the other list's head. Both pointers traverse m+n nodes and meet at the intersection (or null) — the switch equalizes the length difference. Alternatives: length difference alignment, or a hash set of visited nodes (O(m) space).