Given the heads of two singly linked lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection, return null.
The intersection is defined by reference, not value — the two lists share the same node object from the intersection point onward (the tails are physically the same nodes).
Input encoding (3 lines): list A's non-shared prefix, list B's non-shared prefix, then the shared tail (empty ⇒ no intersection). The judge reports the index of your returned node within [A-prefix ++ B-prefix ++ shared] (-1 for null).
- The number of nodes of listA is in the range [0, 3*10^4] - The number of nodes of listB is in the range [0, 3*10^4] - -10^5 <= Node.val <= 10^5 - The lists intersect by reference or not at all
For each node in list A, walk all of list B looking for the same node object. The first match (by reference) is the intersection. No extra memory, but quadratic time.
O(n·m) time, O(1) space.
Put every node of list A into a hash set. Then walk list B; the first node already in the set is the intersection. Linear time at the cost of O(n) memory.
O(n+m) time, O(n) space.
Walk two pointers, one from each head. When a pointer reaches the end, redirect it to the other list's head. After at most one switch each, both pointers have travelled n + m steps and land on the intersection simultaneously (or on null together if there is none).
O(n+m) time, O(1) space.
