Intersection Point of Two Linked Lists in DSA Go - 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 pointer value — both pointers hold the same *ListNode address in memory. In Go, pointer equality is checked with == on pointer types, which compares memory addresses directly, making intersection detection clean and explicit.

Why it matters

Go passes structs by value but pointers by reference, making pointer identity fundamental to data structure manipulation, graph traversal, and concurrent data sharing. This problem sharpens the distinction between pointer equality (same address) and value equality (same data). The two-pointer path-swap technique also appears in cycle detection, palindrome checking, and sliding window problems — all common interview topics.

Where it fits

You need comfort with Go pointer types, linked list traversal, and the difference between *ListNode == *ListNode (pointer comparison) and comparing struct fields before tackling this. After mastering it, Floyd's cycle detection, merging sorted lists, and channel-based concurrent list processing 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 → nil
List B:  2 → 4 ─────┘

pA: 1→3→5→8→10→nil → 2→4→[8] ✓
pB: 2→4→8→10→nil → 1→3→5→[8] ✓
Both reach the same *ListNode{Val:8} simultaneously.

Build-Up - 6 Steps

1

Foundation

Pointer Equality in Go — == on Pointer Types

Concept: == on *ListNode compares memory addresses, not the struct values they point to.

In Go, variables of type *ListNode hold memory addresses. pA == pB is true only when both hold the same address — they point to the same ListNode struct in heap memory. To compare node values you would write pA.Val == pB.Val — a completely different check. Intersection detection requires pointer equality (same address), not value equality (same fields).

Result

You can reliably detect a true memory intersection using == on *ListNode pointers.

Go's == on pointer types is always address comparison. There is no operator overloading — pA == pB checks addresses cleanly without any custom comparison function.

2

Foundation

Brute Force — O(m×n) Nested Loop

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

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

Result

Correct baseline establishing == as the intersection check.

Verifying brute force works via == locks in the correct mental model: same address = intersection. No custom comparator needed in Go.

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 nil. 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 nil, the first common address 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 nil, redirect it to the head of the other list.

Initialize pA = headA, pB = headB. Each step advance both. When pA == nil, set pA = headB. When pB == nil, set pB = headA. Continue until pA == pB. Both traverse lenA + lenB nodes total. If no intersection, both reach nil together. In Go: for pA != pB { if pA == nil { pA = headB } else { pA = pA.Next }; if pB == nil { pB = headA } else { pB = pB.Next } }

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 — nil == nil in Go

🤔Before reading on: in Go, does nil == nil evaluate to true for pointer types? Commit yes or no.

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

If no intersection exists, after each pointer traverses both lists, pA == nil and pB == nil at the same step. In Go, nil == nil is true for pointer types — the zero value of any pointer is nil and all nil pointers of the same type compare equal. So pA != pB evaluates to false and the loop exits cleanly. Return nil.

Result

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

Go's nil is the zero value for pointer types. nil == nil is guaranteed true. The termination condition works universally without any extra counter or flag.

6

Expert

Map Approach — Space Tradeoff in Go

🤔Before reading on: can you store all node pointers from list A in a map[*ListNode]bool and check list B against it? What is the space cost? Commit to your answer.

Concept: Store all node pointers from list A in a map keyed by *ListNode, then scan list B.

In Go: visited := make(map[*ListNode]bool). Traverse list A: visited[node] = true. Traverse list B — first node where visited[node] is true is the intersection. Time O(m+n), space O(m). Go maps use pointer identity as the key for pointer types by default — no custom hash function needed. Simpler to implement but uses extra memory.

Result

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

Go map[*ListNode]bool uses pointer address as the key — exactly what we need for reference identity tracking. No custom hash or equality function required.

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 nil, both arrive at that *ListNode address 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?

Go linked lists are pointer-based struct chains managed by the GC. The path-swap avoids explicit length computation by exploiting arithmetic symmetry. Go's garbage collector tracks all pointer references — nodes in the shared tail are reachable from both list heads and will not be collected until both heads go out of scope. This is transparent to the algorithm.

Step trace (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,...}        nil→headA
  5    nil→headB        &{1,...}
  6    &{2,...}         &{3,...}
  7    &{4,...}         &{5,...}
  8    &{8,...}==&{8,...}  ← pA == pB ✓

Myth Busters - 4 Common Misconceptions

Quick: does pA.Val == pB.Val confirm intersection in Go? Commit yes or no.

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

Reality: Intersection requires pA == pB (same pointer/address). Two separate ListNode structs with the same Val are not the same node.

Why it matters: Comparing Val instead of pointers produces false positives on lists with duplicate values — a silent bug that compiles without warning and produces wrong output.

Quick: does nil == nil evaluate to true for *ListNode in Go? Commit yes or no.

Common Belief: nil == nil might be false or cause a panic in Go.

Reality: nil == nil is true for pointer types in Go. The zero value of *ListNode is nil and all nil *ListNode pointers compare equal.

Why it matters: Fearing nil comparison leads to unnecessary conditional guards around the loop termination, adding complexity and potential off-by-one bugs.

Quick: does the path-swap loop risk an index-out-of-bounds panic when pointers reach nil? Commit yes or no.

Common Belief: The loop will panic when pA or pB becomes nil because we dereference nil pointers.

Reality: The loop condition pA != pB only compares pointer values — it never dereferences them. Dereferencing only happens inside the loop body via pA.Next, and we guard that with the nil check before redirecting.

Why it matters: Correct implementation guards nil before accessing .Next. The comparison itself is always safe.

Quick: does Go's map[*ListNode]bool need a custom hash function for pointer keys? Commit yes or no.

Common Belief: You need to implement a custom hash function to use *ListNode as a map key in Go.

Reality: Go maps support any comparable type as key. Pointer types are comparable by address in Go — map[*ListNode]bool works out of the box with no custom implementation.

Why it matters: Wasting time implementing a custom hash for a type that already works as a map key is a common Go newcomer mistake.

Expert Zone

1

The path-swap requires exactly one redirect per pointer. A second redirect would make pA travel lenA + 2×lenB and pB travel lenB + 2×lenA — only equal when lenA == lenB, destroying the general solution.

2

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

3

Go's escape analysis may allocate ListNode structs on the stack if they don't outlive their function scope — but shared tail nodes must be heap-allocated since they're referenced by both list heads. This is handled transparently by the compiler.

When NOT to use

If lists may contain cycles, pointers never reach nil and the redirect never fires — detect and break cycles first using Floyd's algorithm. If using value semantics (ListNode values, not pointers), == compares struct fields, not addresses — this approach only works with *ListNode pointer types.

Production Patterns

Pointer intersection detection appears in Go runtime internals (detecting aliased slice headers), concurrent data structure debugging (finding shared nodes between goroutines), and graph algorithm libraries (shared node detection in DAGs). The path-swap principle generalizes to any two-sequence synchronization where a shared suffix must be located efficiently.

Connections

Floyd's Cycle Detection in Go

Both use two-pointer synchronization with mathematically guaranteed meeting points, operating purely on pointer comparisons.

Intersection detection and cycle detection share the same core insight: carefully chosen pointer movement rules force convergence without extra memory.

Go Pointer Semantics — Value vs Pointer Receivers

The entire problem hinges on Go's pointer equality — == on *ListNode compares addresses, not struct fields. This is the same distinction that governs value vs pointer receivers, interface satisfaction, and map key comparability in Go.

This problem is a practical drill on one of Go's most important distinctions — mastering it prevents silent bugs across all pointer-based data structures.

Go map[*T]bool for Visited Sets

Go maps use pointer address as the key for pointer types by default — making map[*ListNode]bool a natural, zero-configuration visited set for reference identity tracking.

Knowing Go maps support pointer keys natively removes a common misconception and enables clean visited-set patterns in graph and tree algorithms.

Common Pitfalls

#1 Comparing node values instead of pointer addresses.

Wrong approach:

for pA != nil && pB != nil {
if pA.Val == pB.Val { // WRONG — value comparison
return pA
}
pA = pA.Next
pB = pB.Next
}

Correct approach:

for pA != pB { // Correct — pointer comparison
if pA == nil {
pA = headB
} else {
pA = pA.Next
}
if pB == nil {
pB = headA
} else {
pB = pB.Next
}
}
return pA

Root cause:

In Go, == on pointer types compares addresses. pA.Val == pB.Val compares integer field values — a completely different check that produces false positives on lists with duplicate values.

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

Wrong approach:

pA = pA.Next
if pA == nil {
pA = headB
pA = pA.Next // WRONG — skips headB
}

Correct approach:

if pA == nil {
pA = headB
} else {
pA = pA.Next
}
// Redirect replaces the advance, not follows it

Root cause:

Advancing past nil before redirecting skips headB's first node, breaking distance symmetry by exactly one step and causing the algorithm to miss the intersection.

#3 Dereferencing a nil pointer inside the loop condition causing a panic.

Wrong approach:

for pA.Val != pB.Val { // PANIC if pA or pB is nil
if pA == nil { pA = headB } else { pA = pA.Next }
if pB == nil { pB = headA } else { pB = pB.Next }
}

Correct approach:

for pA != pB { // Safe — pointer comparison, no dereference
if pA == nil { pA = headB } else { pA = pA.Next }
if pB == nil { pB = headA } else { pB = pB.Next }
}
return pA

Root cause:

Dereferencing a nil pointer in Go causes a runtime panic. The loop condition must compare pointers directly (pA != pB), never dereference them.

Key Takeaways

Intersection means the same pointer address (pA == pB in Go) — never compare .Val for intersection detection.

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

nil == nil is true for *ListNode in Go — both pointers reaching nil simultaneously terminates the loop cleanly when no intersection exists.

Go map[*ListNode]bool uses pointer address as key by default — no custom hash or equality function 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 term intersection point mean in the context of two singly linked lists?

easy

A. The last node of the shorter linked list.

B. The node where the values of both lists are equal but references differ.

C. The first node of the longer linked list.

D. The node where both linked lists share the same reference, meaning they merge.

Solution

1. Step 1: Understand linked list nodes and references

   Each node in a linked list has a reference (pointer) to the next node. Two lists intersect if they share the same node reference at some point.

2. Step 2: Define intersection point

   The intersection point is the node where both lists merge and continue as one, sharing the same reference.

3. Final Answer:

   The node where both linked lists share the same reference, meaning they merge. -> Option D

4. Quick Check:

   Intersection means shared node reference [OK]

Hint: Intersection means same node reference, not just same value [OK]

Common Mistakes:

• Confusing same value with same reference
• Thinking intersection is at the start of lists
• Assuming intersection means equal length

2. Which of the following Go function signatures correctly represents a function to find the intersection point of two singly linked lists?

easy

A. func getIntersectionNode(headA ListNode, headB *ListNode) *ListNode

B. func getIntersectionNode(headA ListNode, headB ListNode) ListNode

C. func getIntersectionNode(headA *ListNode, headB *ListNode) *ListNode

D. func getIntersectionNode(headA *ListNode, headB *ListNode) int

Solution

1. Step 1: Understand Go pointer usage for linked lists

   Linked list nodes are usually handled via pointers to allow traversal and modification. So parameters should be pointers.

2. Step 2: Check return type for intersection node

   The function should return a pointer to the intersecting node or nil if none, so return type is *ListNode.

3. Final Answer:

   func getIntersectionNode(headA *ListNode, headB *ListNode) *ListNode -> Option C

4. Quick Check:

   Use pointers for nodes and return pointer [OK]

Hint: Use pointers for linked list nodes in Go function signatures [OK]

Common Mistakes:

• Passing nodes by value instead of pointer
• Returning wrong type like int instead of node pointer
• Mixing pointer and non-pointer parameters

3. Given the following Go code snippet, what will be printed?

type ListNode struct {
    Val  int
    Next *ListNode
}

func main() {
    common := &ListNode{Val: 8, Next: &ListNode{Val: 10, Next: nil}}
    listA := &ListNode{Val: 3, Next: &ListNode{Val: 7, Next: common}}
    listB := &ListNode{Val: 99, Next: &ListNode{Val: 1, Next: common}}

    intersection := getIntersectionNode(listA, listB)
    if intersection != nil {
        fmt.Println(intersection.Val)
    } else {
        fmt.Println(-1)
    }
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    nodes := make(map[*ListNode]bool)
    for headA != nil {
        nodes[headA] = true
        headA = headA.Next
    }
    for headB != nil {
        if nodes[headB] {
            return headB
        }
        headB = headB.Next
    }
    return nil
}

medium

A. 10

B. 8

C. -1

D. 3

Solution

1. Step 1: Understand the linked lists and common node

   listA: 3 -> 7 -> 8 -> 10 listB: 99 -> 1 -> 8 -> 10 The common node starts at value 8.

2. Step 2: Trace getIntersectionNode function

   The function stores all nodes of listA in a map. Then it checks nodes of listB. The first node in listB found in map is the intersection: node with value 8.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   First shared node value = 8 [OK]

Hint: Map nodes of first list, check second list for first match [OK]

Common Mistakes:

• Printing value of last node instead of intersection
• Confusing node value with node reference
• Returning nil when intersection exists

4. The following Go function is intended to find the intersection point of two linked lists but has a bug. What is the bug?

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lengthA, lengthB := 0, 0
    currA, currB := headA, headB

    for currA != nil {
        lengthA++
        currA = currA.Next
    }
    for currB != nil {
        lengthB++
        currB = currB.Next
    }

    diff := lengthA - lengthB
    if diff < 0 {
        diff = -diff
        for i := 0; i < diff; i++ {
            headA = headA.Next
        }
    } else {
        for i := 0; i < diff; i++ {
            headB = headB.Next
        }
    }

    for headA != nil && headB != nil {
        if headA == headB {
            return headA
        }
        headA = headA.Next
        headB = headB.Next
    }
    return nil
}

medium

A. The function incorrectly advances headA when diff < 0 instead of headB.

B. The function does not handle the case when one list is empty.

C. The pointers headA and headB are advanced incorrectly when diff < 0.

D. The diff calculation should be absolute value before advancing pointers.

Solution

1. Step 1: Analyze pointer advancement logic

   If lengthA < lengthB (diff < 0), the shorter list is A, so we should advance headB to align lengths, but code advances headA incorrectly.

2. Step 2: Identify correct pointer to advance

   When diff < 0, advance headB by |diff| steps, else advance headA. The code does the opposite.

3. Final Answer:

   The function incorrectly advances headA when diff < 0 instead of headB. -> Option A

4. Quick Check:

   Advance pointer of longer list, not shorter [OK]

Hint: Advance pointer of longer list by difference in length [OK]

Common Mistakes:

• Advancing pointer of shorter list instead of longer
• Not taking absolute value of length difference
• Ignoring empty list cases

5. You have two singly linked lists that may or may not intersect. Write a Go function that returns the intersection node using the two-pointer technique without extra space. Which of the following code snippets correctly implements this approach?

hard

A. func getIntersectionNode(headA, headB *ListNode) *ListNode {
if headA == nil || headB == nil {
return nil
}
pA, pB := headA, headB
for pA != pB {
if pA == nil {
pA = headB
} else {
pA = pA.Next
}
if pB == nil {
pB = headA
} else {
pB = pB.Next
}
}
return pA
}

B. func getIntersectionNode(headA, headB *ListNode) *ListNode {
visited := make(map[*ListNode]bool)
for headA != nil {
visited[headA] = true
headA = headA.Next
}
for headB != nil {
if visited[headB] {
return headB
}
headB = headB.Next
}
return nil
}

C. func getIntersectionNode(headA, headB *ListNode) *ListNode {
lengthA, lengthB := 0, 0
currA, currB := headA, headB
for currA != nil {
lengthA++
currA = currA.Next
}
for currB != nil {
lengthB++
currB = currB.Next
}
diff := lengthA - lengthB
if diff < 0 {
diff = -diff
for i := 0; i < diff; i++ {
headA = headA.Next
}
} else {
for i := 0; i < diff; i++ {
headB = headB.Next
}
}
for headA != nil && headB != nil {
if headA == headB {
return headA
}
headA = headA.Next
headB = headB.Next
}
return nil
}

D. func getIntersectionNode(headA, headB *ListNode) *ListNode {
for headA != nil {
for headB != nil {
if headA == headB {
return headA
}
headB = headB.Next
}
headA = headA.Next
}
return nil
}

Solution

1. Step 1: Understand two-pointer technique

   Two pointers start at heads of each list. When a pointer reaches end, it switches to the other list's head. They meet at intersection or nil.

2. Step 2: Analyze code snippets

   func getIntersectionNode(headA, headB *ListNode) *ListNode { if headA == nil || headB == nil { return nil } pA, pB := headA, headB for pA != pB { if pA == nil { pA = headB } else { pA = pA.Next } if pB == nil { pB = headA } else { pB = pB.Next } } return pA } correctly implements this logic with pointer switching and loop until pointers meet. func getIntersectionNode(headA, headB *ListNode) *ListNode { visited := make(map[*ListNode]bool) for headA != nil { visited[headA] = true headA = headA.Next } for headB != nil { if visited[headB] { return headB } headB = headB.Next } return nil } uses extra space (map). func getIntersectionNode(headA, headB *ListNode) *ListNode { lengthA, lengthB := 0, 0 currA, currB := headA, headB for currA != nil { lengthA++ currA = currA.Next } for currB != nil { lengthB++ currB = currB.Next } diff := lengthA - lengthB if diff < 0 { diff = -diff for i := 0; i < diff; i++ { headA = headA.Next } } else { for i := 0; i < diff; i++ { headB = headB.Next } } for headA != nil && headB != nil { if headA == headB { return headA } headA = headA.Next headB = headB.Next } return nil } uses length difference method. func getIntersectionNode(headA, headB *ListNode) *ListNode { for headA != nil { for headB != nil { if headA == headB { return headA } headB = headB.Next } headA = headA.Next } return nil } is inefficient nested loops.

3. Final Answer:

   Option A code snippet correctly implements two-pointer technique without extra space. -> Option A

4. Quick Check:

   Two-pointer switch method = func getIntersectionNode(headA, headB *ListNode) *ListNode { if headA == nil || headB == nil { return nil } pA, pB := headA, headB for pA != pB { if pA == nil { pA = headB } else { pA = pA.Next } if pB == nil { pB = headA } else { pB = pB.Next } } return pA } [OK]

Hint: Switch pointers to other list head when reaching end [OK]

Common Mistakes:

• Using extra space instead of two-pointer method
• Not switching pointers after reaching list end
• Using nested loops causing O(n^2) time