Intersection of Two Linked Lists asks for the node where two singly linked lists merge, or None if they never meet. The hash set answer is easy; interviewers are waiting for the O(1) space version.
Count both lengths, advance the longer list's pointer by the difference, then walk both together until they point at the same node. It is clear and correct, and a good first answer.
Walk pointer a through list A then list B, and pointer b through list B then list A. Both travel the same total distance, lenA + lenB, so they line up at the intersection, or both reach None at the same time when there is no intersection.
def get_intersection(headA, headB):
a, b = headA, headB
while a is not b:
a = a.next if a else headB
b = b.next if b else headA
return a
Stress that the comparison is by node identity, not by value; two lists can share values without sharing nodes. Explain why the loop terminates: after at most lenA + lenB steps both pointers are either on the shared node or both None.
One list empty, intersection at the very first node, lists of equal length, and no intersection at all. Walk the no-intersection case on paper, because that is where candidates worry about an infinite loop.
I collect walkthroughs like this while working on the Linkjob AI copilot, which helps people during technical interviews. Disclosure: I help build Linkjob AI.