Intersection of two linked lists

Find the node where two lists merge into a shared tail, using two pointers that swap lists instead of measuring lengths.

The idea

Send pa down list A and pb down list B. When a pointer falls off the end of its own list, redirect it to the other list's head instead of stopping. That cancels out the difference in length, so after at most lenA + lenB steps both pointers are the same number of steps from the end — which means they land on the same node.

Code

public static ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pa = headA, pb = headB;
    while (pa != pb) {
        pa = pa == null ? headB : pa.next;
        pb = pb == null ? headA : pb.next;
    }
    return pa;
}

Tips

• No need to measure either list's length up front; the head-swap does that work for you.
• If the lists never share a tail, both pointers become null on the same step and the loop returns null.

In the .NET library

pa != pb compares node identity (are these the same object?), not value equality — two different nodes that happen to hold equal numbers would never make this loop stop.