Intersection Point of Two Linked Lists in DSA Go - Execution Trace

Concept Flow - Intersection Point of Two Linked Lists

Start at head of List A and List B

↓

Traverse both lists simultaneously

↓

If pointer reaches end, switch to other list's head

↓

Check if pointers are equal (intersection)

Yes No↓

Return intersection

↓

Done

Start pointers at heads of both lists, move forward. When a pointer reaches the end, switch it to the other list's head. Continue until pointers meet or both reach end (no intersection).

Execution Sample

DSA Go

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    a, b := headA, headB
    for a != b {
        if a == nil {
            a = headB
        } else {
            a = a.Next
        }
        if b == nil {
            b = headA
        } else {
            b = b.Next
        }
    }
    return a
}

Two pointers traverse both lists; when reaching end, switch to other list head. They meet at intersection or nil.

Execution Table

Step	Operation	Pointer A	Pointer B	Visual State	Notes
1	Start	Node A1	Node B1	List A: A1->A2->C1->C2->C3 List B: B1->B2->B3->C1->C2->C3	Pointers at heads
2	Move forward	Node A2	Node B2	Pointers move to next nodes	No intersection yet
3	Move forward	Node C1	Node B3	Pointers at C1 and B3	No intersection yet
4	Move forward	Node C2	Node C1	Pointers at C2 and C1	No intersection yet
5	Move forward	Node C3	Node C2	Pointers at C3 and C2	No intersection yet
6	Move forward	nil	Node C3	Pointer A reached end, pointer B at C3	Switch pointer A to headB next step
7	Switch pointer A to headB, move pointer B forward	Node B1	nil	Pointer B reached end	Switch pointer B to headA next step
8	Move forward	Node B2	Node A1	Pointers at B2 and A1	No intersection yet
9	Move forward	Node B3	Node A2	Pointers at B3 and A2	No intersection yet
10	Move forward	Node C1	Node C1	Pointers meet at C1	Intersection found
11	Return intersection	Node C1	Node C1	Intersection node C1	End traversal

💡 Pointers meet at Node C1, intersection found

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	Final
Pointer A	Node A1	Node A2	Node C2	nil	Node B2	Node C1	Node C1
Pointer B	Node B1	Node B2	Node C1	Node C3	Node A1	Node C1	Node C1

Key Moments - 3 Insights

Why do we switch pointer A to headB when it reaches the end of list A?

Switching pointer A to headB ensures it traverses list B after finishing list A, aligning lengths so both pointers meet at intersection or end. See execution_table step 6 and 7.

What happens if there is no intersection between the two lists?

Both pointers will eventually become nil after traversing both lists fully without meeting. The loop ends when a == b == nil, meaning no intersection. This is implied after step 11 if no intersection found.

Why do pointers meet at the intersection node and not before?

Because after switching heads, pointers traverse equal total lengths. They align at the intersection node, as shown in execution_table step 10 where both pointers point to Node C1.

Visual Quiz - 3 Questions

Look at the execution_table, what node is Pointer A at after step 4?

A Node A2

B Node B3

C Node C2

D Node C1

💡 Hint

Check the 'Pointer A' column in execution_table row for step 4.

At which step do both pointers first point to the same node?

A Step 6

B Step 10

C Step 8

D Step 3

💡 Hint

Look for the first row where 'Pointer A' and 'Pointer B' columns have the same node.

If list B was longer by one node before intersection, how would the pointer switching change?

A Pointer B would switch to headA later

B Pointer A would switch to headB later

C Pointers would meet earlier

D Pointers would never meet

💡 Hint

Consider how pointer B traverses list B fully before switching to list A.

Concept Snapshot

Intersection Point of Two Linked Lists:
- Use two pointers starting at heads of each list.
- Move pointers forward one node at a time.
- When a pointer reaches end, switch it to the other list's head.
- Continue until pointers meet (intersection) or both are nil (no intersection).
- This aligns traversal lengths to find intersection efficiently.

Full Transcript

To find the intersection point of two linked lists, we use two pointers starting at the heads of each list. We move both pointers forward one node at a time. When a pointer reaches the end of its list, we switch it to the head of the other list. This way, both pointers traverse the combined lengths of the two lists. Eventually, if there is an intersection, the pointers will meet at the intersection node. If not, both pointers will become nil, indicating no intersection. This method ensures both pointers travel equal distances, aligning them to detect the intersection efficiently.

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