Intersection Point of Two Linked Lists in DSA C++

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. The intersection point is where both roads become the same path. To find it, walk from the start of each road, but if one road is longer, start walking later so both reach the merge point together.

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 first node where both lists intersect (node with value 4).

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

List A length=5, List B length=3

Why: Knowing lengths helps align the start points for comparison

Step 2: Advance pointer in longer list (A) by difference (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 to traverse

Step 3: Move both pointers forward together until they meet

Pointers at node 4 -> 5 -> null

Why: First node where pointers are same is intersection

Step 4: Return node with value 4 as intersection point

Intersection found at node 4

Why: This node is shared by both lists

Result:

4 -> 5 -> null is the intersection starting point

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int getLength(ListNode* head) {
    int length = 0;
    while (head) {
        length++;
        head = head->next;
    }
    return length;
}

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    int lenA = getLength(headA);
    int lenB = getLength(headB);

    // Advance the longer list by the difference in lengths
    while (lenA > lenB) {
        headA = headA->next; // advance headA
        lenA--;
    }
    while (lenB > lenA) {
        headB = headB->next; // advance headB
        lenB--;
    }

    // Move both pointers until they meet
    while (headA && headB) {
        if (headA == headB) {
            return headA; // intersection found
        }
        headA = headA->next; // advance both
        headB = headB->next;
    }
    return nullptr; // no intersection
}

int main() {
    // Shared nodes
    ListNode* node4 = new ListNode(4);
    ListNode* node5 = new ListNode(5);
    node4->next = node5;

    // List A: 1->2->3->4->5
    ListNode* headA = new ListNode(1);
    headA->next = new ListNode(2);
    headA->next->next = new ListNode(3);
    headA->next->next->next = node4;

    // List B: 9->4->5
    ListNode* headB = new ListNode(9);
    headB->next = node4;

    ListNode* intersection = getIntersectionNode(headA, headB);
    if (intersection) {
        ListNode* curr = intersection;
        while (curr) {
            cout << curr->val;
            if (curr->next) cout << " -> ";
            curr = curr->next;
        }
        cout << " -> null" << endl;
    } else {
        cout << "No intersection" << endl;
    }
    return 0;
}

int lenA = getLength(headA); int lenB = getLength(headB);

Calculate lengths of both lists to find difference

while (lenA > lenB) { headA = headA->next; lenA--; }

Advance longer list pointer to align both lists

while (lenB > lenA) { headB = headB->next; lenB--; }

Advance longer list pointer to align both lists

while (headA && headB) { if (headA == headB) return headA; headA = headA->next; headB = headB->next; }

Move both pointers together until intersection or end

Output

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: Naive approach compares every node of one list with every node of the other, O(m*n), which is much slower

Edge Cases

One or both lists are empty

Returns no intersection (nullptr)

DSA C++

while (headA && headB) { if (headA == headB) return headA; ... }

Lists do not intersect

Returns no intersection (nullptr)

DSA C++

return nullptr; // no intersection

Intersection at head node

Returns head node as intersection

DSA C++

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 intersection point pattern by aligning lengths and moving pointers together.

Common Mistakes

Mistake: Not aligning the longer list pointer before moving both pointers
Fix: Calculate lengths and advance the longer list pointer by the difference before simultaneous traversal

Mistake: Comparing node values instead of node addresses
Fix: Compare node pointers (addresses) to detect intersection, not values

Summary

Finds the first shared node where two linked lists intersect.

Use when you need to detect if two linked lists merge and find the merge point.

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

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