160. Intersection of Two Linked Lists

Time: O(m + n)

Space: O(1)

Intuition

If both pointers walk the same total distance (|A| + |B|), they will arrive at the intersection at the same step - or both arrive at null together if there is no intersection. Redirecting each pointer to the other list's head when it reaches null achieves exactly this total-distance equality with no extra memory.

Algorithm

1Initialise a = headA, b = headB.
2While a != b: advance each by one step. When a reaches null, redirect it to headB. When b reaches null, redirect it to headA.
3If the lists intersect, a == b will be the intersection node. If not, both will be null simultaneously (null == null).
4Return a (or b).

Example Walkthrough

Input: A = [4,1,8,4,5], B = [5,6,1,8,4,5] (intersect at node with value 8)

1.a walks A (5 nodes) then B (6 nodes) = 11 steps to reach node 8.
2.b walks B (6 nodes) then A (5 nodes) = 11 steps to reach node 8.
3.At step 11, a == b == the intersection node.

Output: Reference to node with value 8

Common Pitfalls

•Compare node references, not node values - multiple nodes can have the same value but only one is the true intersection.
•The loop exits when a == b (including both being null for non-intersecting lists). Do NOT check a != null.

160.cs

// Approach: Two pointers a and b start at the heads of lists A and B respectively.
// Each advances one step at a time. When a reaches null, redirect it to headB; likewise b → headA.
// Both pointers travel a total of |A| + |B| steps, so they arrive at the intersection simultaneously.
// If the lists do not intersect, both reach null at the same time (null == null ends the loop).
// The cross-traversal cancels out the length difference — no need to compute list lengths.
// Time: O(m + n) Space: O(1) — no extra data structures needed.

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}

public class Solution
{
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
    {
        if (headA == null || headB == null) return null;

        ListNode a = headA;
        ListNode b = headB;

        while (a != b)
        {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
}

Was this solution helpful?