Intersection Point of Two Linked Lists in DSA Python - Deep Dive

Overview - Intersection Point of Two Linked Lists

What is it?

Given two singly linked lists that may share a common tail, find the node where they first merge. Both lists point to the same node object — not just the same value — so the intersection is a physical junction in memory where one pointer sequence meets another.

Why it matters

This problem trains you to think about pointer identity vs value equality, a distinction critical in system programming, memory management, and graph traversal. It also introduces the two-pointer synchronization technique which reappears in cycle detection, string comparison, and sliding window problems.

Where it fits

You need to be comfortable with linked list traversal and pointer manipulation before tackling this. After mastering this, you are ready for Floyd's cycle detection, merging sorted lists, and clone with random pointer problems.

Mental Model

Core Idea

If two runners start from different points but travel the same total distance by switching paths, they will meet exactly at the intersection.

Think of it like...

Imagine two hiking trails of different lengths that merge onto a single shared path. If hiker A walks trail A then trail B, and hiker B walks trail B then trail A, both cover the same total distance. They step onto the shared path at exactly the same moment.

List A:  1 → 3 → 5 ─┐
                       ├→ 8 → 10 → NULL
List B:  2 → 4 ─────┘

Pointer pA: 1→3→5→8→10→NULL → 2→4→[8] ✓
Pointer pB: 2→4→8→10→NULL → 1→3→5→[8] ✓
Both reach node 8 simultaneously.

Build-Up - 6 Steps

1

Foundation

Understanding the Problem — Pointer Identity

Concept: Intersection means the same node object, not the same value.

Two linked lists intersect when a node in list A IS the same object as a node in list B — meaning they share the same memory address. All nodes after the intersection are also shared. Two nodes with value 8 in different lists do NOT intersect unless they are literally the same object.

Result

You can distinguish a true intersection from coincidental equal values.

This identity-vs-equality distinction is the single most important conceptual point in the problem.

2

Foundation

Brute Force — Check Every Pair

Concept: For each node in list A, scan all of list B for a matching address.

Loop through every node in list A. For each node, loop through every node in list B. If the addresses match (nodeA is nodeB), return that node. Time complexity O(m×n), space O(1). This establishes a correct baseline before optimizing.

Result

Correct solution but too slow for large lists.

Understanding why brute force works confirms your grasp of pointer identity, which all optimized solutions build on.

3

Intermediate

Length Difference Approach

🤔Before reading on: if list A has length 6 and list B has length 4, where should each pointer start so they reach the end at the same time? Commit to your answer.

Concept: Advance the pointer of the longer list by the length difference, then walk both in sync.

Compute lengths lenA and lenB. If lenA > lenB, advance pointer A by (lenA - lenB) steps. Now both pointers are equidistant from the end. Walk both one step at a time. The first node where pA is pB is the intersection. Time O(m+n), space O(1).

Result

Efficient single-pass-after-alignment solution.

Aligning tails by length difference is the key insight that removes the offset problem.

4

Intermediate

Two-Pointer Path-Swap Technique

🤔Before reading on: if pA travels list A then list B, and pB travels list B then list A, do they cover the same total distance? Commit yes or no.

Concept: When a pointer reaches NULL, redirect it to the head of the other list.

Start pA at headA and pB at headB. Each step, advance both. When pA reaches NULL, set pA = headB. When pB reaches NULL, set pB = headA. Continue until pA is pB. Both pointers now travel lenA + lenB total steps, so they arrive at the intersection simultaneously. If no intersection, both reach NULL together.

Result

Elegant O(m+n) time, O(1) space solution with no length computation needed.

The path swap equalizes total travel distance, making separate length calculation unnecessary.

5

Advanced

Handling No Intersection

🤔Before reading on: what happens to pA and pB in the path-swap approach when the lists do not intersect? Commit to your answer.

Concept: Both pointers reach NULL at the same step when there is no intersection.

If no intersection exists, pA and pB will both eventually become NULL at the same step (after each has traversed both lists). The loop condition pA != pB terminates when both are NULL since None == None is True. Return None to indicate no intersection.

Result

The same algorithm handles both intersecting and non-intersecting cases cleanly.

No special case needed — the math works out regardless of whether intersection exists.

6

Expert

Hash Set Approach — Space-Time Tradeoff

🤔Before reading on: can you store all nodes of list A in a set and then check list B against it? What is the space cost? Commit to your answer.

Concept: Store all node references from list A in a hash set, then scan list B.

Traverse list A and add every node to a set. Then traverse list B — the first node found in the set is the intersection. Time O(m+n), space O(m). This is simpler to implement but uses extra memory. In interviews, always mention this before presenting the O(1) space solution.

Result

Correct O(m+n) solution at the cost of O(m) memory.

Knowing the hash set approach demonstrates systematic thinking; dismissing it for space shows depth.

Under the Hood

The two-pointer path-swap works because pointer A travels distance lenA + lenB and pointer B travels distance lenB + lenA. Both cover identical total distance. If an intersection exists at distance d from the end, both pointers arrive at it after exactly lenA + lenB - d steps. The offset caused by different starting distances is cancelled by the path swap.

Why designed this way?

Linked lists do not support random access, so index-based alignment is impossible. The path-swap avoids computing lengths explicitly by exploiting symmetry: a + b = b + a. This mirrors Floyd's cycle detection in using two pointers with carefully chosen movement rules to guarantee a meeting point.

Step-by-step pointer positions (A:1→3→5→8→10, B:2→4→8→10):

Step  pA    pB
  0    1     2
  1    3     4
  2    5     8
  3    8    10
  4   10  NULL→headA=1
  5  NULL→headB=2   1
  6    2     3
  7    4     5
  8   [8]   [8]  ← MEET

Myth Busters - 4 Common Misconceptions

Quick: does intersection mean two nodes have the same value? Commit yes or no.

Common Belief: Two nodes intersect if they have the same value.

Reality: Intersection means the same memory address — the same node object, not just the same value.

Why it matters: Comparing values instead of references produces wrong answers on lists with duplicate values.

Quick: in the path-swap approach, do pA and pB meet after exactly lenA steps? Commit yes or no.

Common Belief: The two pointers meet after one of them completes its own list.

Reality: They meet after each pointer has traversed both lists combined, which takes lenA + lenB - intersectionDepth steps.

Why it matters: Misunderstanding the meeting condition leads to incorrect termination logic and off-by-one bugs.

Quick: if the lists do not intersect, does the two-pointer loop run forever? Commit yes or no.

Common Belief: The algorithm loops infinitely when no intersection exists.

Reality: Both pointers become NULL simultaneously after traversing both lists, terminating the loop cleanly.

Why it matters: Believing an infinite loop exists causes developers to add unnecessary cycle-break conditions that break correct cases.

Quick: does returning None from the function mean the algorithm failed? Commit yes or no.

Common Belief: Returning None indicates a bug in the algorithm.

Reality: None is the correct return value when no intersection exists — it is a valid, expected output.

Why it matters: Treating None as failure causes incorrect error handling and missed edge case coverage.

Expert Zone

1

The path-swap technique requires exactly two redirections total (one per pointer) — adding a third redirect breaks the distance symmetry and causes an infinite loop.

2

If both lists have the same length, the pointers naturally stay synchronized from the start and no redirect is needed for the first pass — the algorithm still terminates correctly.

3

The problem assumes no cycles in either list. If cycles exist, run Floyd's algorithm first to detect and handle them before searching for intersection.

When NOT to use

If lists can contain cycles, the path-swap approach will loop infinitely at the cycle rather than reaching NULL for redirection. In that case, use hash sets or break cycles first. If memory is not a constraint and implementation speed matters, the hash set approach is simpler and equally correct.

Production Patterns

In production graph traversal or memory graph analysis tools, intersection detection is used to find aliased references — two variables pointing to the same object. The path-swap principle generalizes to detecting where two traversal sequences converge, which appears in version control (merge base detection) and dependency graph analysis.

Connections

Floyd's Cycle Detection

Both use two-pointer synchronization to guarantee a meeting point through mathematical distance equalization.

Understanding intersection detection makes Floyd's algorithm more intuitive — both exploit pointer arithmetic rather than brute comparison.

Merge Base in Git

Git's merge base algorithm finds the common ancestor of two branches, analogous to finding the common tail of two linked lists.

The path-swap idea — walk both histories and find where they converge — directly maps to how version control finds divergence points.

Clone Linked List with Random Pointer

Both problems require distinguishing node identity from node value across two linked structures.

Mastering pointer identity here makes the random pointer clone problem significantly easier to reason about.

Common Pitfalls

#1 Comparing node values instead of node references.

Wrong approach:

while pA and pB:
if pA.val == pB.val: # WRONG — compares values
return pA
pA = pA.next
pB = pB.next

Correct approach:

while pA != pB: # Correct — compares object identity
pA = pA.next if pA else headB
pB = pB.next if pB else headA
return pA

Root cause:

Confusing value equality with reference equality — two different nodes can have the same value without being the same object.

#2 Redirecting the pointer to the other head AFTER advancing past NULL, causing a one-step skip.

Wrong approach:

pA = pA.next
if pA is None:
pA = headB
pA = pA.next # WRONG — skips headB

Correct approach:

pA = pA.next if pA else headB
# Redirect happens IN the advance step, not after

Root cause:

Separating the NULL check from the advance causes the first node of the other list to be skipped, breaking distance symmetry.

#3 Not handling the case where one or both lists are empty.

Wrong approach:

def getIntersectionNode(headA, headB):
pA, pB = headA, headB
while pA != pB: # Crashes if headA or headB is None immediately

Correct approach:

def getIntersectionNode(headA, headB):
if not headA or not headB:
return None
pA, pB = headA, headB
while pA != pB:
pA = pA.next if pA else headB
pB = pB.next if pB else headA
return pA

Root cause:

Skipping null guards on inputs causes AttributeError on .next access when an empty list is passed.

Key Takeaways

Intersection means the same node object in memory, not equal values — always compare references with 'is' or '!=' on node objects.

The path-swap two-pointer technique equalizes total travel distance so both pointers arrive at the intersection simultaneously without computing list lengths.

When no intersection exists, both pointers reach NULL at the same step, terminating the loop cleanly — no special case needed.

The hash set approach trades O(m) space for simpler implementation — always worth mentioning before presenting the O(1) space solution in interviews.

This technique generalizes to any problem where two sequences must be synchronized by their distance from a common endpoint.