Intersection Point of Two Linked Lists in DSA C++ - Execution Trace

Concept Flow - Intersection Point of Two Linked Lists

Start with two heads: headA, headB

↓

Traverse both lists simultaneously

↓

If pointerA reaches end, switch to headB

↓

If pointerB reaches end, switch to headA

↓

Check if pointerA == pointerB

↓

Intersection

↓

Repeat until intersection or both null

Start traversing both lists with two pointers. When a pointer reaches the end, switch it to the other list's head. Continue until pointers meet or both reach null.

Execution Sample

DSA C++

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
  ListNode* a = headA;
  ListNode* b = headB;
  while (a != b) {
    a = a ? a->next : headB;
    b = b ? b->next : headA;
  }
  return a;
}

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

Execution Table

Step	Operation	Pointer A	Pointer B	Visual State
1	Start	Node A1	Node B1	List A: A1 -> A2 -> C1 -> C2 -> C3 List B: B1 -> B2 -> B3 -> C1 -> C2 -> C3
2	Compare pointers	A1	B1	No match, move both forward
3	Move pointers	A2	B2	Pointers moved to next nodes
4	Compare pointers	A2	B2	No match, move both forward
5	Move pointers	C1	B3	Pointers moved to next nodes
6	Compare pointers	C1	B3	No match, move both forward
7	Move pointers	C2	C1	Pointers moved to next nodes
8	Compare pointers	C2	C1	No match, move both forward
9	Move pointers	C3	C2	Pointers moved to next nodes
10	Compare pointers	C3	C2	No match, move both forward
11	Move pointers	null	C3	Pointer A reached end, switch to headB; Pointer B moved forward
12	Compare pointers	B1	C3	No match, move both forward
13	Move pointers	B2	null	Pointer A moved forward; Pointer B reached end, switch to headA
14	Compare pointers	B2	A1	No match, move both forward
15	Move pointers	B3	A2	Pointers moved to next nodes
16	Compare pointers	B3	A2	No match, move both forward
17	Move pointers	C1	C1	Pointers moved to next nodes
18	Compare pointers	C1	C1	Match found! Intersection at C1
19	Return	C1	C1	Intersection node returned

💡 Pointers meet at node C1, intersection found.

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
Pointer A	A1	A2	C1	C2	C3	null	B1	B2	B3	C1	null	B1	B2	B2	B3	B3	C1	C1	C1
Pointer B	B1	B2	B3	C1	C2	C3	C3	null	A1	A2	C1	C3	null	A1	A2	A2	C1	C1	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 both pointers traverse equal total lengths, allowing them to meet at the intersection if it exists. See execution_table steps 11 and 13 where pointers switch lists.

What happens if the lists do not intersect?

Both pointers will eventually become null after traversing both lists fully, causing the loop to exit without finding an intersection. This is implied by the exit condition in the code and the loop ending when a == b (both null).

Why do we compare pointers directly instead of node values?

We compare pointers because intersection means the exact same node in memory, not just equal values. Execution_table step 18 shows pointers matching by reference, not value.

Visual Quiz - 3 Questions

Look at the execution_table at step 11, what happens to pointer A?

A Pointer A moves to next node in list A

B Pointer A reaches end of list A and switches to headB

C Pointer A becomes null and stops

D Pointer A moves to headA again

💡 Hint

Check the 'Operation' and 'Pointer A' columns at step 11 in execution_table

At which step do pointers first point to the intersection node?

A Step 18

B Step 15

C Step 10

D Step 19

💡 Hint

Look for the first 'Match found' in the 'Operation' column of execution_table

If list B was shorter and had no intersection, what would happen to the pointers?

A Pointer A would reach null but pointer B would not

B They would loop infinitely

C They would meet at null after traversing both lists

D They would meet at the last node of list A

💡 Hint

Refer to key_moments about no intersection and exit conditions

Concept Snapshot

Intersection Point of Two Linked Lists:
- Use two pointers starting at heads of each list.
- Move pointers forward; switch to other list head when reaching end.
- Pointers meet at intersection or both become null.
- Compare pointers by reference, not value.
- Time: O(m+n), Space: O(1).

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, it switches to the head of the other list. This way, both pointers traverse the same total length. Eventually, if the lists intersect, the pointers will meet at the intersection node. If not, both pointers will become null, ending the search. We compare pointers directly to check if they point to the same node in memory. This method runs in linear time and uses constant extra space.

Practice

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

easy

A. The last node of each linked list.

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

C. The first node of the longer linked list.

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

Solution

1. Step 1: Understand linked list nodes

   Each node in a linked list has a value and a reference (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 D

4. Quick Check:

   Intersection means shared node reference = A [OK]

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

Common Mistakes:

• Confusing same value with same node reference
• Thinking intersection is the last node always
• Assuming intersection means equal length lists

2. Which of the following C++ code snippets correctly declares a singly linked list node structure for intersection detection?

easy

A. struct Node { int data; Node* next; };

B. struct Node { int data; Node next; };

C. struct Node { int data; Node* next(){}; };

D. struct Node { int data; Node next(); };

Solution

1. Step 1: Understand pointer usage in C++ structs

   A linked list node must have a pointer to the next node, so Node* next; is correct.

2. Step 2: Analyze options

   struct Node { int data; Node* next; }; uses Node* next; which is correct. Options A, B, and D misuse pointer or function syntax.

3. Final Answer:

   struct Node { int data; Node* next; }; -> Option A

4. Quick Check:

   Pointer to next node = C [OK]

Hint: Use pointer (*) for next node in struct [OK]

Common Mistakes:

• Forgetting the * pointer for next node
• Using function syntax instead of pointer
• Declaring next as object instead of pointer

3. Given two linked lists intersecting at node with value 7, what will the following code print?

Node* getIntersectionNode(Node* headA, Node* headB) {
    Node* a = headA;
    Node* b = headB;
    while (a != b) {
        a = a ? a->next : headB;
        b = b ? b->next : headA;
    }
    return a;
}

// Lists:
// A: 3 -> 6 -> 9 -> 7 -> 10
// B: 1 -> 7 -> 10

Node* intersection = getIntersectionNode(headA, headB);
if (intersection) std::cout << intersection->data << std::endl;
else std::cout << -1 << std::endl;

medium

A. -1

B. 10

C. 7

D. 3

Solution

1. Step 1: Understand the algorithm

   This code uses two pointers traversing both lists; when one reaches end, it switches to the other list's head. They meet at intersection.

2. Step 2: Trace the pointers

   Both pointers meet at node with value 7, which is the intersection point.

3. Final Answer:

   7 -> Option C

4. Quick Check:

   Intersection node data = 7 [OK]

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

Common Mistakes:

• Assuming intersection is node with value 10
• Printing -1 when intersection exists
• Confusing node value with node reference

4. Identify the bug in this code snippet that tries to find the intersection point of two linked lists:

Node* getIntersection(Node* headA, Node* headB) {
    while (headA != headB) {
        headA = headA->next;
        headB = headB->next;
    }
    return headA;
}

medium

A. It does not handle different list lengths, causing null pointer errors.

B. It uses incorrect comparison operator for nodes.

C. It returns the wrong node after loop ends.

D. It should use recursion instead of iteration.

Solution

1. Step 1: Analyze pointer movement

   The code moves both pointers forward simultaneously without adjusting for different list lengths.

2. Step 2: Identify consequence

   If lists differ in length, one pointer may reach null before the other, causing a null pointer dereference or infinite loop.

3. Final Answer:

   It does not handle different list lengths, causing null pointer errors. -> Option A

4. Quick Check:

   Unequal lengths cause errors = D [OK]

Hint: Adjust pointers for length difference before comparing [OK]

Common Mistakes:

• Ignoring list length difference
• Dereferencing null pointers
• Assuming simultaneous traversal always works

5. You have two singly linked lists that intersect. List A has length 8, List B has length 5. Which approach correctly finds the intersection point efficiently?

hard

A. Traverse both lists fully and store nodes in hash sets, then find first common node.

B. Calculate length difference, advance longer list by difference, then move both pointers together.

C. Reverse both lists and compare nodes from start until they differ.

D. Compare node values one by one from heads until a matching value is found.

Solution

1. Step 1: Understand length difference method

   Calculate difference (8 - 5 = 3), advance longer list by 3 nodes to align both lists.

2. Step 2: Traverse both lists together

   Move both pointers one step at a time; the first node where they match is the intersection.

3. Final Answer:

   Calculate length difference, advance longer list by difference, then move both pointers together. -> Option B

4. Quick Check:

   Align by length difference then traverse = B [OK]

Hint: Advance longer list by length difference before simultaneous traversal [OK]

Common Mistakes:

• Comparing node values instead of references
• Reversing lists unnecessarily
• Using extra space when not needed