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.