Intersection Point of Two Linked Lists in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Intersection Point Detection

What is the output of the following C++ code that finds the intersection point of two linked lists?

DSA C++

struct Node {
    int data;
    Node* next;
    Node(int x) : data(x), next(nullptr) {}
};

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

int main() {
    Node* common = new Node(8);
    common->next = new Node(10);

    Node* headA = new Node(3);
    headA->next = new Node(7);
    headA->next->next = common;

    Node* headB = new Node(99);
    headB->next = new Node(1);
    headB->next->next = common;

    Node* intersection = getIntersectionNode(headA, headB);
    if (intersection) {
        std::cout << intersection->data << std::endl;
    } else {
        std::cout << "No intersection" << std::endl;
    }
    return 0;
}

A 8

B 10

C No intersection

D 7

💡 Hint

Trace the pointers moving through both lists until they meet.

The code uses two pointers starting at heads of each list. They traverse and switch lists when reaching the end. They meet at the intersection node with value 8.

🧠 Conceptual

intermediate

Understanding the Two Pointer Technique

Why does the two-pointer technique used in finding the intersection point of two linked lists work?

A Because the pointers move randomly and eventually meet by chance.

B Because both pointers traverse equal total lengths by switching heads, they meet at intersection or end.

C Because the pointers only traverse their own lists without switching.

D Because the pointers use recursion to find the intersection.

💡 Hint

Think about the total distance each pointer travels.

Each pointer traverses both lists fully, so if there is an intersection, they align at the intersection node after equal steps.

🔧 Debug

advanced

Identify the Bug in Intersection Code

What error will the following code produce when trying to find the intersection point of two linked lists?

DSA C++

struct Node {
    int data;
    Node* next;
    Node(int x) : data(x), next(nullptr) {}
};

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

A Infinite loop

B Returns correct intersection node

C Segmentation fault (null pointer dereference)

D Compilation error

💡 Hint

Check what happens when a or b is nullptr before accessing next.

The code tries to access a->next without checking if a is nullptr, causing a crash.

❓ Predict Output

advanced

Output of Intersection Detection with No Intersection

What is the output of this code when two linked lists do not intersect?

DSA C++

struct Node {
    int data;
    Node* next;
    Node(int x) : data(x), next(nullptr) {}
};

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

int main() {
    Node* headA = new Node(1);
    headA->next = new Node(2);
    headA->next->next = new Node(3);

    Node* headB = new Node(4);
    headB->next = new Node(5);
    headB->next->next = new Node(6);

    Node* intersection = getIntersectionNode(headA, headB);
    if (intersection) {
        std::cout << intersection->data << std::endl;
    } else {
        std::cout << "No intersection" << std::endl;
    }
    return 0;
}

A 3

B Segmentation fault

C 6

D No intersection

💡 Hint

If no intersection, pointers meet at nullptr.

Both pointers eventually become nullptr at the same time, so the function returns nullptr and prints 'No intersection'.

🚀 Application

expert

Number of Nodes in Intersection Part

Given two singly linked lists that intersect, how can you find the number of nodes in the intersection part (shared tail)?

A Find intersection node, then count nodes from it to end

B Count total nodes in both lists and subtract lengths

C Use a hash set to store all nodes of first list, then count matches in second list

D Traverse both lists simultaneously and count matching nodes from start

💡 Hint

Once you find the intersection node, count nodes from there to the end.

The intersection part is the shared tail starting from the intersection node. Counting nodes from that node to the end gives the length.

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