Intersection Point of Two Linked Lists in DSA Go

Mental Model

Two linked lists may share some nodes at the end. The intersection point is the first shared node. We find it by aligning their lengths and moving together.

Analogy: Imagine two roads merging into one highway. The intersection point is where the two roads join and become the same path.

List A: 1 -> 2 -> 3 -> 4 -> 5 -> null
                     ↑
List B:       9 -> 4 -> 5 -> null
                     ↑
Intersection at node with value 4

Dry Run Walkthrough

Input: List A: 1->2->3->4->5, List B: 9->4->5 (4 and 5 are shared nodes)

Goal: Find the node where the two lists start to share nodes (value 4)

Step 1: Calculate lengths of both lists: lenA=5, lenB=3

List A: 1 -> 2 -> 3 -> 4 -> 5 -> null
List B: 9 -> 4 -> 5 -> null

Why: Knowing lengths helps align the lists to compare nodes at the same distance from the end

Step 2: Advance pointer in longer list (A) by lenA - lenB = 2 steps

List A pointer at node 3 -> 4 -> 5 -> null
List B pointer at node 9 -> 4 -> 5 -> null

Why: Align both pointers so they have equal nodes remaining to traverse

Step 3: Move both pointers forward together until they meet

Pointers at nodes:
A: 3 -> 4 -> 5 -> null
B: 9 -> 4 -> 5 -> null
After move:
A: 4 -> 5 -> null
B: 4 -> 5 -> null

Why: Moving together checks for the first common node

Step 4: Pointers meet at node with value 4

Intersection found at node 4 -> 5 -> null

Why: This is the first shared node, the intersection point

Result:

4 -> 5 -> null is the intersection point

Annotated Code

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func getLength(head *ListNode) int {
    length := 0
    for head != nil {
        length++
        head = head.Next
    }
    return length
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lenA := getLength(headA)
    lenB := getLength(headB)

    // Advance the longer list's pointer by the difference in lengths
    for lenA > lenB {
        headA = headA.Next
        lenA--
    }
    for lenB > lenA {
        headB = headB.Next
        lenB--
    }

    // Move both pointers until they meet or reach the end
    for headA != nil && headB != nil {
        if headA == headB {
            return headA
        }
        headA = headA.Next
        headB = headB.Next
    }
    return nil
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Printf("%d", head.Val)
        if head.Next != nil {
            fmt.Print(" -> ")
        }
        head = head.Next
    }
    fmt.Println(" -> null")
}

func main() {
    // Shared nodes
    shared := &ListNode{Val: 4, Next: &ListNode{Val: 5, Next: nil}}

    // List A: 1 -> 2 -> 3 -> 4 -> 5 -> null
    headA := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: shared}}}

    // List B: 9 -> 4 -> 5 -> null
    headB := &ListNode{Val: 9, Next: shared}

    fmt.Print("List A: ")
    printList(headA)
    fmt.Print("List B: ")
    printList(headB)

    intersection := getIntersectionNode(headA, headB)
    if intersection != nil {
        fmt.Printf("Intersection at node with value %d\n", intersection.Val)
        fmt.Print("Intersection list from node: ")
        printList(intersection)
    } else {
        fmt.Println("No intersection found")
    }
}

lenA := getLength(headA) lenB := getLength(headB)

Calculate lengths of both lists to find difference

for lenA > lenB { headA = headA.Next lenA-- }

Advance pointer in longer list to align both lists

for lenB > lenA { headB = headB.Next lenB-- }

Advance pointer in longer list to align both lists

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

Move both pointers together until intersection or end

Output

List A: 1 -> 2 -> 3 -> 4 -> 5 -> null

List B: 9 -> 4 -> 5 -> null

Intersection at node with value 4

Intersection list from node: 4 -> 5 -> null

Complexity Analysis

Time: O(m + n) because we traverse both lists to get lengths and then traverse aligned parts once

Space: O(1) because we use only pointers and counters, no extra data structures

vs Alternative: Compared to using a hash set to store visited nodes (O(m + n) time and O(m) space), this approach uses constant space

Edge Cases

One or both lists are empty

Function returns nil immediately as no intersection is possible

DSA Go

for headA != nil && headB != nil {

Lists do not intersect

Pointers reach end (nil) without meeting, function returns nil

DSA Go

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

Intersection at head node (both lists are same)

Function returns head immediately as intersection

DSA Go

if headA == headB { return headA }

When to Use This Pattern

When you see two linked lists and need to find if they share nodes, use the length alignment pattern to find the intersection efficiently.

Common Mistakes

Mistake: Comparing node values instead of node references to find intersection
Fix: Compare node pointers (addresses) to detect actual shared nodes, not just equal values

Summary

Finds the first shared node where two linked lists intersect.

Use when you need to detect if two linked lists merge and where.

Align list pointers by length difference, then move together to find intersection.

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