Brute Force Approach for Intersection of Two Linked Lists

The naive approach involves checking every node in the first list against every node in the second list to see if they point to the same memory location.

1. Iterate through headA with a pointer ptrA.
2. For every node visited by ptrA, iterate through the entire list headB using ptrB.
3. Check if ptrA == ptrB (reference equality).
4. If a match is found, return that node.
5. If loops complete without a match, return null.

Pseudo-code:

text
for nodeA in listA:
    for nodeB in listB:
        if nodeA is nodeB:
            return nodeA
return null

Complexity Analysis: The time complexity is $O(m \times n)$, where $m$ and $n$ are the lengths of the two lists. For large inputs (up to $3 \times 10^4$ nodes each), this results in approximately $10^9$ operations, which is highly inefficient and may lead to a Time Limit Exceeded (TLE) error or simply fail the interview constraint of linear time complexity.

Core Insight for Intersection of Two Linked Lists

The fundamental challenge in LeetCode 160 is that the two lists may have different lengths before the intersection point. A pointer traversing the shorter list will reach the intersection sooner than a pointer traversing the longer list.

To solve this, we must synchronize the pointers so they arrive at the intersection simultaneously. The core insight is to virtually "concatenate" the lists.

If a pointer traverses List A and then immediately switches to the head of List B, the total distance it covers is Length(A) + Length(B). Conversely, a pointer traversing List B then List A covers Length(B) + Length(A). Since addition is commutative, both pointers traverse exactly the same total distance.

Visual Description: Imagine two pointers, pA and pB.

1. pA moves through List A. When it hits the end (null), it jumps to the head of List B.
2. pB moves through List B. When it hits the end (null), it jumps to the head of List A.
3. By effectively swapping starting lanes after the first pass, the pointer that started on the longer list has now been delayed exactly enough to align with the pointer that started on the shorter list.
4. They will meet at the intersection node. If there is no intersection, they will both reach null at the exact same step after the swap.

Execution Flow

1. Start: ptrA points to the first node of List A; ptrB points to the first node of List B.
2. Compare: Check if ptrA and ptrB refer to the same object. If yes, return ptrA.
3. Advance:
   • Move ptrA forward. If ptrA was at the last node of List A, move it to the first node of List B.
   • Move ptrB forward. If ptrB was at the last node of List B, move it to the first node of List A.
4. Repeat: Continue this process.
   • If the lists intersect, the pointers will eventually align at the intersection node because the "head start" of the shorter list is canceled out by the length of the longer list during the second pass.
   • If the lists do not intersect, both pointers will traverse len(A) + len(B) nodes and reach null at the same time. The condition ptrA == ptrB (where both are null) satisfies the loop termination.
5. Output: Return the node found (or null).

Proof of Correctness

Let $L_A$ be the length of List A, $L_B$ be the length of List B, and $C$ be the length of the shared suffix (intersection).

• The non-shared part of A is $L_A - C$.
• The non-shared part of B is $L_B - C$.

When ptrA traverses A then B, it travels $(L_A - C)$ nodes (unique A), then $C$ nodes (shared), then switches to B and travels $(L_B - C)$ nodes (unique B) before reaching the intersection again. Total distance to intersection: $(L_A - C) + C + (L_B - C) = L_A + L_B - C$.

When ptrB traverses B then A, it travels $(L_B - C)$ nodes (unique B), then $C$ nodes (shared), then switches to A and travels $(L_A - C)$ nodes (unique A) before reaching the intersection again. Total distance to intersection: $(L_B - C) + C + (L_A - C) = L_A + L_B - C$.

Since the distance to the intersection is identical for both pointers, and they move at the same speed (1 node/step), they are guaranteed to meet at the intersection node. If no intersection exists ($C=0$), they both travel $L_A + L_B$ and meet at null.

Reference Implementation

C++ Solution for LeetCode 160

cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // If either head is null, there is no intersection
        if (!headA || !headB) return nullptr;

        ListNode *ptrA = headA;
        ListNode *ptrB = headB;

        // Traverse until the pointers meet (either at the intersection node or at null)
        while (ptrA != ptrB) {
            // If ptrA reaches the end of listA, switch to headB
            // Otherwise, move to the next node
            ptrA = (ptrA == nullptr) ? headB : ptrA->next;

            // If ptrB reaches the end of listB, switch to headA
            // Otherwise, move to the next node
            ptrB = (ptrB == nullptr) ? headA : ptrB->next;
        }

        // Return the intersection node or null
        return ptrA;
    }
};

Java Solution for LeetCode 160

java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // Boundary check
        if (headA == null || headB == null) return null;

        ListNode ptrA = headA;
        ListNode ptrB = headB;

        // Continue until they collide or both hit null
        while (ptrA != ptrB) {
            // Switch tracks at the end of the list
            ptrA = (ptrA == null) ? headB : ptrA.next;
            ptrB = (ptrB == null) ? headA : ptrB.next;
        }

        return ptrA;
    }
}

Python Solution for LeetCode 160

python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if not headA or not headB:
            return None
        
        ptrA = headA
        ptrB = headB
        
        # Loop until pointers meet or both become None
        while ptrA != ptrB:
            # If ptrA reaches end of list A, redirect to head B
            ptrA = ptrA.next if ptrA else headB
            # If ptrB reaches end of list B, redirect to head A
            ptrB = ptrB.next if ptrB else headA
            
        return ptrA