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

Concept Flow - Intersection Point of Two Linked Lists

Start at head of List A and List B

↓

Traverse both lists simultaneously

↓

If pointerA reaches end, switch to head of List B

↓

If pointerB reaches end, switch to head of List A

↓

Check if pointerA == pointerB

↓

Intersection

↓

End if both pointers are None

We move two pointers through the lists. When one reaches the end, it switches to the other list's head. They meet at the intersection or both become None if no intersection.

Execution Sample

DSA Python

def getIntersectionNode(headA, headB):
    pointerA, pointerB = headA, headB
    while pointerA != pointerB:
        pointerA = pointerA.next if pointerA else headB
        pointerB = pointerB.next if pointerB else headA
    return pointerA

This code finds the intersection node of two linked lists by switching pointers between lists when reaching the end.

Execution Table

Step	Operation	PointerA Node	PointerB Node	PointerA Switch	PointerB Switch	Visual State
1	Initialize pointers	A1	B1	No	No	A1 -> A2 -> C1 -> C2 -> C3 B1 -> B2 -> B3 -> C1 -> C2 -> C3
2	Compare pointerA and pointerB	A1	B1	No	No	Pointers at A1 and B1, not equal
3	Move pointerA and pointerB	A2	B2	No	No	Pointers move to A2 and B2
4	Compare pointerA and pointerB	A2	B2	No	No	Pointers at A2 and B2, not equal
5	Move pointerA and pointerB	C1	B3	No	No	Pointers move to C1 and B3
6	Compare pointerA and pointerB	C1	B3	No	No	Pointers at C1 and B3, not equal
7	Move pointerA and pointerB	C2	C1	No	No	Pointers move to C2 and C1
8	Compare pointerA and pointerB	C2	C1	No	No	Pointers at C2 and C1, not equal
9	Move pointerA and pointerB	C3	C2	No	No	Pointers move to C3 and C2
10	Compare pointerA and pointerB	C3	C2	No	No	Pointers at C3 and C2, not equal
11	Move pointerA and pointerB	None	C3	Yes (to headB)	No	PointerA reached end, switches to headB; pointerB moves to C3
12	Compare pointerA and pointerB	B1	C3	No	No	Pointers at B1 and C3, not equal
13	Move pointerA and pointerB	B2	None	No	Yes (to headA)	PointerB reached end, switches to headA; pointerA moves to B2
14	Compare pointerA and pointerB	B2	A1	No	No	Pointers at B2 and A1, not equal
15	Move pointerA and pointerB	B3	A2	No	No	Pointers move to B3 and A2
16	Compare pointerA and pointerB	B3	A2	No	No	Pointers at B3 and A2, not equal
17	Move pointerA and pointerB	C1	C1	No	No	Pointers move to C1 and C1
18	Compare pointerA and pointerB	C1	C1	No	No	Pointers equal at C1, intersection found
19	Return intersection node	C1	C1	No	No	Intersection node C1 returned

💡 Pointers meet at node C1, intersection found; loop ends.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	After 12	After 13	After 14	After 15	After 16	After 17	Final
pointerA	A1	A2	C1	C2	C3	None	B1	B2	B3	C1	C1	C1	C1	C1	C1	C1	C1	C1	C1
pointerB	B1	B2	B3	C1	C2	C3	C3	None	A1	A2	A2	A2	A2	A2	A2	A2	C1	C1	C1

Key Moments - 3 Insights

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

Switching pointerA to headB ensures both pointers traverse equal total lengths, allowing them to meet at the intersection if it exists. See execution_table step 11 where pointerA switches to headB after reaching None.

What happens if the lists do not intersect?

Both pointers will eventually become None after traversing both lists fully without meeting. The loop ends when pointerA == pointerB == None. This is implied in the concept flow and exit condition.

Why do we compare pointerA and pointerB before moving them?

Comparing before moving catches the intersection node immediately when both pointers point to the same node. See execution_table step 18 where pointers are equal at C1 before moving.

Visual Quiz - 3 Questions

Look at the execution_table at step 11, what happens to pointerA?

A It switches to head of List B

B It moves to next node in List A

C It becomes None and stops

D It switches to head of List A

💡 Hint

Check the 'PointerA Switch' column at step 11 in execution_table.

At which step do pointerA and pointerB first point to the same node?

A Step 10

B Step 17

C Step 18

D Step 19

💡 Hint

Look at the 'PointerA Node' and 'PointerB Node' columns in execution_table where they match.

If the lists had no intersection, what would be the final value of pointerA and pointerB?

A Both would be at the last node of their lists

B Both would be None

C PointerA would be None, pointerB at head

D PointerA at head, pointerB would be None

💡 Hint

Refer to the concept_flow and key_moments about no intersection scenario.

Concept Snapshot

Intersection Point of Two Linked Lists:
- Use two pointers starting at heads of each list.
- Move pointers forward; when reaching end, switch to other list's head.
- Pointers meet at intersection node or both become None if no intersection.
- Time complexity: O(m+n), space: O(1).
- No extra memory needed; pointers traverse equal total length.

Full Transcript

This concept finds the intersection node of two singly linked lists by using two pointers. Each pointer starts at the head of one list. They move forward one node at a time. When a pointer reaches the end of its list, it switches to the head of the other list. This way, both pointers travel the same total distance. If the lists intersect, the pointers meet at the intersection node. If not, both pointers become None at the end, and the function returns None. The execution table shows each step, pointer positions, and when switches happen. Key moments clarify why switching pointers is necessary and how the comparison works before moving pointers. The visual quiz tests understanding of pointer switching, meeting point, and no intersection case.

Practice

1. What does the term intersection point of two linked lists mean?

easy

A. The first node of the longer linked list.

B. The node where both linked lists share the same reference (memory address).

C. The node where the values of both linked lists are equal.

D. The last node of the shorter linked list.

Solution

1. Step 1: Understand linked list nodes

   Each node in a linked list has a value and a reference (memory address) to the next node.

2. Step 2: Define intersection point

   The intersection point is where two linked lists share the exact same node reference, not just the same value.

3. Final Answer:

   The node where both linked lists share the same reference (memory address). -> Option B

4. Quick Check:

   Intersection means shared node reference [OK]

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

Common Mistakes:

• Confusing same value with same node reference
• Thinking intersection is based on node values
• Assuming intersection is always at the start

2. Which of the following Python code snippets correctly initializes two linked lists headA and headB that intersect at node with value 8?

easy

A. headA = Node(3)
headB = Node(99)
headA.next = Node(8)
headB.next = Node(8)

B. node = Node(8)
headA = Node(3, node)
headB = Node(99, node)

C. headA = Node(3)
headB = Node(99)
node = Node(8)
headA.next = node
headB.next = node

D. nodeA = Node(3)
nodeB = Node(99)
nodeC = Node(8)
headA = nodeA
headB = nodeB

Solution

1. Step 1: Understand intersection setup

   To create intersection, both lists must share the same node object for the intersecting node.

2. Step 2: Check code correctness

   headA = Node(3) headB = Node(99) node = Node(8) headA.next = node headB.next = node creates node with value 8 once and assigns it as next for both lists, ensuring intersection.

3. Final Answer:

   headA and headB share the same node object for value 8. -> Option C

4. Quick Check:

   Shared node object creates intersection [OK]

Hint: Intersection needs shared node object, not just same value nodes [OK]

Common Mistakes:

• Creating separate nodes with same value instead of shared node
• Assigning next pointers incorrectly
• Not linking nodes properly

3. What will be the output of the following Python code that finds the intersection point of two linked lists?

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def get_intersection(headA, headB):
    a, b = headA, headB
    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a.val if a else None

# Setup
common = Node(7)
common.next = Node(10)
headA = Node(3)
headA.next = Node(6)
headA.next.next = common
headB = Node(99)
headB.next = common

print(get_intersection(headA, headB))

medium

A. 7

B. 10

C. None

D. 3

Solution

1. Step 1: Understand the intersection nodes

   Both lists share node with value 7 and then 10. Intersection is at node with value 7.

2. Step 2: Trace the get_intersection function

   Pointers a and b traverse lists; when they meet at node 7, function returns 7.

3. Final Answer:

   7 -> Option A

4. Quick Check:

   First shared node value is 7 [OK]

Hint: Two-pointer method returns first shared node value [OK]

Common Mistakes:

• Returning value of second shared node
• Returning None if not careful with pointer resets
• Confusing node values with references

4. The following code attempts to find the intersection point of two linked lists but does not work correctly. What is the main error?

def get_intersection(headA, headB):
    a, b = headA, headB
    while a != b:
        a = a.next
        b = b.next
    return a.val if a else None

medium

A. It returns the value of the last node instead of the intersection.

B. It compares node values instead of node references.

C. It uses incorrect variable names for nodes.

D. It does not reset pointers to the other list when reaching the end.

Solution

1. Step 1: Analyze pointer movement

   The code moves pointers a and b forward but never resets them to the other list's head.

2. Step 2: Understand consequence

   Without resetting, pointers may reach None at different times and never meet, missing intersection.

3. Final Answer:

   It does not reset pointers to the other list when reaching the end. -> Option D

4. Quick Check:

   Resetting pointers is key for intersection detection [OK]

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

Common Mistakes:

• Not resetting pointers causes infinite loop or no detection
• Comparing values instead of references
• Returning wrong node value

5. Given two singly linked lists that may or may not intersect, which approach correctly finds the intersection point in O(m+n) time and O(1) space?

Options:
A) Use two pointers starting at heads; move each pointer to the other list's head when reaching end until they meet.
B) Use a hash set to store nodes of first list, then check nodes of second list for membership.
C) Compare every node of first list with every node of second list.
D) Reverse both lists and compare nodes from the start until mismatch.

hard

A. Two-pointer switching heads method until pointers meet.

B. Hash set membership check for intersection.

C. Nested loops comparing all nodes pairwise.

D. Reverse lists and compare nodes from start.

Solution

1. Step 1: Analyze time and space complexity

   Two-pointer switching heads method until pointers meet. uses two pointers and no extra space, running in O(m+n) time and O(1) space.

2. Step 2: Compare other options

   Hash set membership check for intersection. uses extra space (hash set), Nested loops comparing all nodes pairwise. is O(m*n), Reverse lists and compare nodes from start. modifies lists and is inefficient.

3. Final Answer:

   Two-pointer switching heads method until pointers meet. -> Option A

4. Quick Check:

   Two-pointer method is optimal for intersection [OK]

Hint: Two-pointer switch method finds intersection efficiently [OK]

Common Mistakes:

• Using extra space unnecessarily
• Using nested loops causing slow performance
• Modifying lists destructively