• M, N up to 10,000
• Original list structure must be preserved.
• O(1) extra space required.

Finding the intersection of two linked lists is fundamentally about reconciling the different prefix lengths of the two paths. Our goal is to reach the junction point simultaneously, regardless of how much "extra" list precedes that junction in either list.

The most straightforward approach is to iterate through every node in the first list and, for each node, scan through the entire second list to see if we find a reference match. This is highly inefficient because it performs a nested comparison for every node, resulting in quadratic time complexity.

# Brute force: nested comparison
def brute_force(headA, headB):
    currA = headA
    while currA:
        currB = headB
        while currB:
            if currA == currB: return currA
            currB = currB.next
        currA = currA.next
    return None

By storing all nodes of List A in a set, we can iterate through List B and check if any node exists in the set. The first match is our intersection.

# Hash Set approach
def get_intersection(headA, headB):
    nodes_seen = set()
    while headA:
        nodes_seen.add(headA)
        headA = headA.next
    while headB:
        if headB in nodes_seen: return headB
        headB = headB.next
    return None

If we know the lengths of both lists, we can ignore the extra prefix of the longer list. We calculate the difference d in lengths and advance the pointer of the longer list by d steps. Now, both pointers are equidistant from the junction and will meet after a simultaneous traversal.

# Length-difference approach
def get_intersection(headA, headB):
    lenA, lenB = get_len(headA), get_len(headB)
    while lenA > lenB: headA = headA.next; lenA -= 1
    while lenB > lenA: headB = headB.next; lenB -= 1
    while headA != headB:
        headA = headA.next; headB = headB.next
    return headA

The "Track-Switch" insight elegantly eliminates the need to calculate lengths. If we concatenate the lists (A+B and B+A), both combined paths have the exact same length (M+N). By switching pointers to the other list's head upon reaching the end, the pointers are naturally forced to synchronize their traversal after exactly one swap, meeting at the junction node or null.

# Optimal: track-switching pointers
def get_intersection(headA, headB):
    p1, p2 = headA, headB
    while p1 != p2:
        p1 = p1.next if p1 else headB
        p2 = p2.next if p2 else headA
    return p1

Step 1: Start of Traversal
We place pointer p1 at the head of List A (4) and p2 at the head of List B (5).

Step 2: Traversal Phase
Both pointers walk forward at identical speed. Because the paths before the intersection have different lengths, the pointers reach the intersection node 8 at different times.

Step 3: p1 Switches Tracks
When p1 reaches the end of List A (after node 5), it becomes null and immediately switches to the head of List B (5).

Step 4: p2 Switches Tracks
Next, p2 reaches the end of List B, becomes null, and switches to the head of List A (4).

Step 5: Synchronization & Meeting
Because both pointers have now traveled the exact same combined prefix distance (Length(A) + Length(B)), their offsets are perfectly synchronized. They march forward and meet at the intersection node 8!