The O(n) Club: Linked Lists Intersection — Y-Junctions, Off-By-One Fails, and Pointer Shenanigans

The O(n) Club: Linked Lists Intersection — Y-Junctions, Off-By-One Fails, and Pointer Shenanigans

⚡ TL;DR

Given two singly linked lists that might join hands and skip into the sunset (meaning they reference the same sequence from their Y-shaped intersection), your job is to find that dramatic junction. Not by the values — this is about shared node identity. Brute-force works like searching all of Stack Overflow for your answer, but it’s slow. Here’s what not to ship:

// Brute-force Java: Not for real life!
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    for (ListNode a = headA; a != null; a = a.next) {
        for (ListNode b = headB; b != null; b = b.next) {
            if (a == b) return a;
        }
    }
    return null;
}

🧠 How Devs Usually Mess This Up

If you’ve ever compared node.val instead of real node references, congratulations—you’ve invented the world’s least effective intersection detector. Two nodes with value 7 are just awkward lookalikes. Also, people love to assume the lists always intersect—newsflash: sometimes they’re just ships passing in the night, never meeting. Handle the null, or prepare for NullPointerException bingo!

🔍 What’s Actually Going On

Picture two delivery robots rolling down different warehouse aisles. They start separately, but one day, they find themselves carrying the same box (that’s your shared node). From that point, their paths are (literally) identical. You need to find out when they stopped being strangers and started working from the same warehouse manifest (aka, reference equality).

🛠️ PseudoCode

• Start two pointers: One on list A (pA), one on B (pB).
• March both forward: At each step, if you run off the tail (null), teleport your pointer to the other list’s head (yes, magical).
• Meet-cute logic: The first time pA == pB, you’ve found the intersection or they both hit null (aka, no intersection: eternal loneliness).

// Java flavor pseudocode
a = headA; b = headB;
while (a != b) {
    a = (a == null) ? headB : a.next;
    b = (b == null) ? headA : b.next;
}
// a is now either the intersection node or null.

No need to measure, sort, or juggle counts. Eventually, both pointers walk exactly the same ground by swapping paths—so their sync-up is as inevitable as a coffee spill on your keyboard.

💻 The Code

// ListNode definition provided by Leetcode/most platforms
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode a = headA, b = headB;
    while (a != b) {
        a = (a == null) ? headB : a.next;
        b = (b == null) ? headA : b.next;
    }
    return a;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Value twins aren’t real intersections: Don’t trust node.val—only trust node == otherNode.
• No intersection? Solution returns null. Yes, that’s allowed.
• Circular lists? If you encounter infinity, you’re in the wrong problem. Go debug your input.
• Performance reality check: O(m + n) time and O(1) space—interviewers love this (and so will your RAM).

🧠 Interviewer Brain-Tattoo

“Comparing node values is like swiping right on a profile picture instead of meeting in person. Don’t get catfished by integer values—check references!”