Intersection Point of Two Linked Lists in DSA C# - 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. Intersection means the same object reference — both pointers hold the exact same ListNode instance in heap memory. In C#, object reference equality is checked with Object.ReferenceEquals(pA, pB) or simply pA == pB when no operator== override exists on the class.

Why it matters

C# is a managed language with a garbage collector, but reference identity is still fundamental for linked list manipulation, graph traversal, and object graph analysis. This problem sharpens the distinction between reference equality (same object) and value equality (same data), a distinction that affects LINQ, dictionary keys, and collection membership throughout C# development.

Where it fits

You need comfort with C# class references, linked list traversal, and the difference between == and .Equals() before tackling this. After mastering it, Floyd's cycle detection, merging sorted lists, and WeakReference-based caching follow naturally.

Mental Model

Core Idea

If two runners start from different points but each runs both paths in sequence, they cover the same total distance and meet exactly where the paths merge.

Think of it like...

Two roads of different lengths merge onto one shared highway. Driver A takes road A then road B; driver B takes road B then road A. Both drive the same total distance and enter the shared highway at exactly the same moment.

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

pA: 1→3→5→8→10→null → 2→4→[8] ✓
pB: 2→4→8→10→null → 1→3→5→[8] ✓
Both reach the same ListNode instance {val=8} simultaneously.

Build-Up - 6 Steps

1

Foundation

Reference Equality in C# — == vs .Equals() vs ReferenceEquals()

Concept: For class types without operator== override, == checks reference identity (same heap address).

In C#, ListNode is typically a class (reference type). For reference types without a custom == operator, pA == pB checks whether both variables point to the same object on the heap — identical to Object.ReferenceEquals(pA, pB). Two distinct ListNode objects with the same val are NOT equal by ==. Use pA == pB for intersection — never pA.val == pB.val.

Result

You can reliably detect intersection using == on ListNode references.

C#'s default == for class types is reference equality. This makes intersection detection natural — pA == pB is the correct check without any custom comparer.

2

Foundation

Brute Force — O(m×n) Nested Loop

Concept: For every node in list A, scan all of list B checking reference equality.

Outer loop traverses list A. Inner loop traverses list B. If pA == pB (same reference), return that node. Time O(m×n), space O(1). Correct but slow — confirms reference equality is the right check before optimizing.

Result

Correct baseline establishing == as the intersection check.

Seeing brute force work via == on class instances locks in the mental model: same reference = intersection. No custom IEqualityComparer needed.

3

Intermediate

Length Difference Approach

🤔Before reading on: if list A has 6 nodes and list B has 4, how many steps should the longer pointer advance before walking both in sync? Commit to your answer.

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

Count lenA and lenB. If lenA > lenB, advance pA by (lenA - lenB) steps. Both are now equidistant from null. Walk both one step per iteration. First node where pA == pB is the intersection. Time O(m+n), space O(1).

Result

Efficient O(m+n) solution after tail alignment.

Once aligned at equal distance from null, the first common reference must be the intersection.

4

Intermediate

Two-Pointer Path-Swap Technique

🤔Before reading on: if pA traverses list A then list B, and pB traverses list B then list A, do both cover the same total number of nodes? Commit yes or no.

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

Initialize pA = headA, pB = headB. Each step advance both. When pA == null, set pA = headB. When pB == null, set pB = headA. Continue until pA == pB. Both traverse lenA + lenB nodes total, arriving at the intersection simultaneously. If no intersection, both reach null together.

Result

Elegant O(m+n) time, O(1) space with no length variables.

lenA + lenB == lenB + lenA. The path swap exploits arithmetic symmetry to cancel the starting offset without any measurement.

5

Advanced

No Intersection — null == null in C#

🤔Before reading on: in C#, does null == null evaluate to true for reference types? Commit yes or no.

Concept: Both pointers become null simultaneously when no intersection exists, terminating the loop.

If no intersection exists, after each pointer traverses both lists, pA == null and pB == null at the same step. In C#, null == null is true for reference types, so pA != pB evaluates to false and the while loop exits cleanly. Return null.

Result

No special case needed — the same loop handles both intersecting and non-intersecting cases.

C# null comparisons are well-defined: null == null is always true for reference types. No NullReferenceException occurs from the comparison itself — only from dereferencing a null pointer.

6

Expert

HashSet Approach — Space Tradeoff in C#

🤔Before reading on: can you store all ListNode references from list A in a HashSet and check list B against it? What is the space cost? Commit to your answer.

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

var visited = new HashSet(). Traverse list A: visited.Add(node). Traverse list B — first node where visited.Contains(node) is true is the intersection. Time O(m+n), space O(m). HashSet uses Object.GetHashCode() and Object.Equals() by default for class types, both of which are identity-based for classes without override — exactly what we need.

Result

Correct O(m+n) solution at O(m) space cost.

C# HashSet uses reference-based GetHashCode() and Equals() by default for classes without override — no custom IEqualityComparer needed for reference identity tracking.

Under the Hood

The path-swap works because pA travels lenA + lenB nodes and pB travels lenB + lenA nodes — identical totals. If an intersection exists at distance d from null, both arrive at that node after lenA + lenB - d steps. The different starting positions contribute lenA and lenB to each pointer's first leg and lenB and lenA to the second — the offset cancels exactly.

Why designed this way?

C# linked lists are reference-type object chains managed by the GC. The path-swap avoids explicit length computation by exploiting arithmetic symmetry. The GC tracks all references to shared nodes — nodes in the intersected tail are reachable from both list heads and will not be collected until both are released. This is safe and correct under C#'s memory model.

Step trace (A: 1→3→5→8→10, B: 2→4→8→10):

Step  pA                pB
  0    ListNode{val=1}   ListNode{val=2}
  1    ListNode{val=3}   ListNode{val=4}
  2    ListNode{val=5}   ListNode{val=8}
  3    ListNode{val=8}   ListNode{val=10}
  4    ListNode{val=10}  null→headA
  5    null→headB        ListNode{val=1}
  6    ListNode{val=2}   ListNode{val=3}
  7    ListNode{val=4}   ListNode{val=5}
  8    [same ref val=8] == [same ref val=8] ✓

Myth Busters - 4 Common Misconceptions

Quick: does pA.val == pB.val confirm intersection in C#? Commit yes or no.

Common Belief: Two nodes intersect if their val fields are equal.

Reality: Intersection requires pA == pB (same reference). Two distinct ListNode objects with the same val are not the same node.

Why it matters: Comparing val instead of references produces false positives on lists with duplicate values — a common C# mistake when confusing value and reference equality.

Quick: should you use Object.ReferenceEquals() instead of == for intersection detection? Commit yes or no.

Common Belief: You must always use Object.ReferenceEquals() for safe reference comparison in C#.

Reality: For a class without operator== override (like typical ListNode), == is already reference equality — identical to ReferenceEquals(). Either works; == is more idiomatic.

Why it matters: Over-using ReferenceEquals() adds verbosity without benefit. Understanding when == is reference equality vs value equality is a core C# skill.

Quick: does the path-swap loop risk a NullReferenceException when pointers reach null? Commit yes or no.

Common Belief: Comparing null == null or null != pB might throw NullReferenceException.

Reality: Null comparison (pA == null, pA != pB) never throws NullReferenceException — only dereferencing null (pA.val, pA.next) does. The loop condition pA != pB is always safe.

Why it matters: Fear of NullReferenceException leads to unnecessary null guards around comparisons, adding complexity. Comparisons are safe; dereferences are what need guarding.

Quick: does HashSet need a custom IEqualityComparer for reference identity? Commit yes or no.

Common Belief: HashSet needs a custom IEqualityComparer to compare by reference.

Reality: For classes without GetHashCode/Equals override, HashSet uses the default identity-based implementations inherited from Object — no custom comparer needed.

Why it matters: Writing an unnecessary custom comparer wastes time and risks bugs. Knowing the defaults saves effort and produces cleaner code.

Expert Zone

1

The path-swap requires exactly one redirect per pointer. A second redirect breaks distance symmetry — both pointers would travel different total distances and never meet at the intersection.

2

If both lists have equal length, the pointers stay naturally synchronized from step one and find the intersection (or reach null together) without any redirect.

3

C#'s GC uses reference counting and tracing — nodes in the shared tail are kept alive as long as either list head is reachable. This is transparent to the algorithm but important for memory analysis tools.

When NOT to use

If ListNode overrides operator== to compare by value (unusual but possible), pA == pB would use value equality and produce wrong results. In that case, explicitly use Object.ReferenceEquals(pA, pB). If lists may contain cycles, use HashSet or break cycles first — the null-redirect never fires in a cyclic list.

Production Patterns

Reference intersection detection appears in C# object graph analyzers (.NET memory profilers), AST node sharing detection in Roslyn compiler analysis, and dependency injection container debugging (detecting shared service instances). The path-swap principle generalizes to any two-sequence synchronization where a shared suffix must be located efficiently.

Connections

Floyd's Cycle Detection

Both use two-pointer synchronization with mathematically guaranteed meeting points rather than brute reference comparison.

Mastering intersection detection makes Floyd's algorithm intuitive — both reduce to: move two pointers with specific rules and they will meet at a meaningful reference.

C# Reference vs Value Equality (== vs .Equals() vs ReferenceEquals())

The entire problem hinges on knowing that == on class types without override is reference equality — the same distinction that governs string interning, record types, and collection membership in C#.

This problem is a practical drill on one of C#'s most important type system distinctions — mastering it prevents bugs across LINQ queries, dictionary keys, and HashSet membership.

C# HashSet<T> Default Equality

HashSet uses reference-based GetHashCode/Equals by default for classes — making it natural for reference identity tracking without any comparer.

Understanding that object identity is the default equality for reference types makes HashSet the correct tool for reference-based visited sets throughout graph and tree algorithms.

Common Pitfalls

#1 Comparing .val instead of object references.

Wrong approach:

while (pA != null && pB != null) {
if (pA.val == pB.val) // WRONG — value comparison
return pA;
pA = pA.next;
pB = pB.next;
}

Correct approach:

while (pA != pB) { // Correct — reference comparison
pA = pA != null ? pA.next : headB;
pB = pB != null ? pB.next : headA;
}
return pA;

Root cause:

For class types, == is reference equality. pA.val == pB.val compares int fields — a completely different check that produces false positives on duplicate values.

#2 Advancing past null before redirecting, skipping the first node of the other list.

Wrong approach:

pA = pA.next;
if (pA == null) {
pA = headB;
pA = pA.next; // WRONG — skips headB
}

Correct approach:

pA = pA != null ? pA.next : headB;
// Redirect is part of the ternary advance expression

Root cause:

Separating the null check from the advance skips headB's first node, breaking distance symmetry by exactly one step.

#3 Using a custom IEqualityComparer that compares by value in HashSet.

Wrong approach:

// Custom comparer comparing node values — WRONG for intersection
var visited = new HashSet(new NodeValueComparer());
// visited.Contains(node) now matches by val, not by reference

Correct approach:

// Default HashSet — uses reference identity automatically
var visited = new HashSet();
// visited.Contains(node) correctly matches by reference

Root cause:

A value-based comparer makes the HashSet match any node with the same val — producing false positives. Reference identity is the correct equality for intersection detection.

Key Takeaways

Intersection means the same object reference (pA == pB in C#) — never compare .val for intersection detection.

For class types without operator== override, C#'s == is reference equality — identical to Object.ReferenceEquals().

null == null is true in C# for reference types — both pointers reaching null simultaneously terminates the loop cleanly when no intersection exists.

HashSet uses reference-based equality by default for classes — no custom IEqualityComparer needed for reference identity tracking.

Exactly one redirect per pointer is required — a second redirect breaks distance symmetry and causes incorrect results.

Practice

1. What does the "Intersection Point of Two Linked Lists" problem ask you to find?

easy

A. The node where two linked lists merge or start sharing nodes

B. The length of the longer linked list

C. The sum of all node values in both lists

D. The last node of the first linked list

Solution

1. Step 1: Understand the problem goal

   The problem asks to find the node where two linked lists merge or start sharing nodes, meaning they have a common reference from that node onward.

2. Step 2: Differentiate from other concepts

   It is not about length, sum, or last node alone, but about the exact node where both lists intersect.

3. Final Answer:

   The node where two linked lists merge or start sharing nodes -> Option A

4. Quick Check:

   Intersection means shared node = A [OK]

Hint: Look for the first common node reference in both lists [OK]

Common Mistakes:

• Confusing intersection with equal values instead of shared nodes
• Thinking intersection means same length
• Looking for sum or last node instead of merge point

2. Which of the following C# code snippets correctly declares a singly linked list node class for this problem?

easy

A. class Node { int val; Node next; Node(int x) { val = x; next = null; } }

B. public class ListNode { int val; ListNode next; ListNode() { val = 0; next = null; } }

C. public struct ListNode { int val; ListNode next; }

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

Solution

1. Step 1: Check for correct access modifiers and constructor

   public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } } uses public fields and a constructor that initializes value and next pointer properly.

2. Step 2: Identify issues in other options

   class Node { int val; Node next; Node(int x) { val = x; next = null; } } lacks public keyword, so fields are private by default; public struct ListNode { int val; ListNode next; } uses struct which is not typical for linked lists; public class ListNode { int val; ListNode next; ListNode() { val = 0; next = null; } } has no constructor parameter and fields are private.

3. Final Answer:

   public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } } -> Option D

4. Quick Check:

   Public class with constructor = B [OK]

Hint: Use public fields and constructor with parameter for node value [OK]

Common Mistakes:

• Omitting public keyword causing access issues
• Using struct instead of class for nodes
• Not initializing next pointer to null

3. What will be the output of the following C# code snippet that finds the intersection point of two linked lists? public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } } public class Solution { public ListNode GetIntersectionNode(ListNode headA, ListNode headB) { ListNode a = headA, b = headB; while (a != b) { a = (a == null) ? headB : a.next; b = (b == null) ? headA : b.next; } return a; } } // Setup lists ListNode common = new ListNode(8); common.next = new ListNode(10); ListNode headA = new ListNode(3); headA.next = new ListNode(7); headA.next.next = common; ListNode headB = new ListNode(99); headB.next = common; Solution sol = new Solution(); ListNode result = sol.GetIntersectionNode(headA, headB); Console.WriteLine(result.val);

medium

A. 99

B. 8

C. 7

D. 10

Solution

1. Step 1: Understand the linked list setup

   List A: 3 -> 7 -> 8 -> 10; List B: 99 -> 8 -> 10. The intersection node is the node with value 8.

2. Step 2: Trace the GetIntersectionNode method

   Two pointers traverse lists; when one reaches end, it switches to the other list head. They meet at intersection node 8.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   Intersection node value = 8 [OK]

Hint: Pointers switch lists to align lengths and meet at intersection [OK]

Common Mistakes:

• Confusing node values instead of node references
• Assuming intersection is last node always
• Not switching pointers to other list head

4. Identify the bug in this C# method intended to find the intersection point of two linked lists: public ListNode GetIntersectionNode(ListNode headA, ListNode headB) { ListNode a = headA, b = headB; while (a != b) { a = a.next; b = b.next; if (a == null && b == null) return null; } return a; }

medium

A. It uses incorrect comparison operator for nodes

B. It returns null too early when both pointers are null

C. It does not switch pointers to the other list when reaching null

D. It does not handle empty lists

Solution

1. Step 1: Analyze pointer movement in the loop

   Both pointers move forward but never switch to the other list head when reaching null, so they may never meet.

2. Step 2: Understand the consequence

   Without switching, if lists differ in length, pointers become null at different times and miss intersection.

3. Final Answer:

   It does not switch pointers to the other list when reaching null -> Option C

4. Quick Check:

   Switch pointers at null to find intersection [OK]

Hint: Switch pointers to other list head when null to align traversal [OK]

Common Mistakes:

• Not switching pointers causes infinite loop or wrong result
• Returning null too early without full traversal
• Confusing node equality with value equality

5. Given two singly linked lists that may or may not intersect, which approach correctly finds the intersection node in O(m+n) time and O(1) space? Options: A) Use two pointers starting at heads; when a pointer reaches end, switch it to the other list's head; continue until they meet. B) Use a hash set to store nodes of first list, then check nodes of second list for presence. C) Calculate lengths of both lists, advance longer list pointer by difference, then move both pointers until node.val match. D) Reverse both lists and compare nodes from start until mismatch. Which is the best approach for this problem?

hard

A. Two pointers switching heads when reaching end

B. Hash set to store nodes of first list

C. Advance longer list pointer by length difference then compare node.val

D. Reverse both lists and compare nodes

Solution

1. Step 1: Evaluate time and space complexity of each approach

   Two pointers switching heads when reaching end uses two pointers switching heads, runs in O(m+n) time and O(1) space.

2. Step 2: Compare with other options

   Hash set to store nodes of first list uses extra space O(m); Advance longer list pointer by length difference then compare node.val is incorrect because it compares values instead of node references; Reverse both lists and compare nodes is destructive and inefficient.

3. Step 3: Choose the best approach

   Two pointers switching heads when reaching end is clean, efficient, and uses constant space without modifying lists.

4. Final Answer:

   Two pointers switching heads when reaching end -> Option A

5. Quick Check:

   Two-pointer switch method = A [OK]

Hint: Use two pointers switching heads for O(1) space and linear time [OK]

Common Mistakes:

• Using extra space unnecessarily
• Modifying lists by reversing
• Comparing node values instead of references