Kickstarting Our DSA Journey: Learning and Growing Together

Introduction

Two minds. One goal — learning out loud.

Hey everyone!
We’re two friends kicking off a beginner-friendly learning series — a place to learn, teach, and build logic together.
The goal? Slowly create a community to support engineers out there on the same journey.

Today, we’re starting with: Intersection of Two Linked Lists — a classic problem to sharpen your understanding of linked lists and pointers.

Problem Recap

We are given two singly linked lists, headA and headB. They might merge at some point, meaning from that node onward they share the same memory reference. Your task: return the node where the intersection starts. If the lists never meet, return null.

Example:

Source - Leetcode

Intersection: node c1.

Remember: Intersection is by reference, not by value.

Brute Force Approach

Idea:
Check every node in list A against every node in list B. If any node is the same object in memory, that’s the intersection.

Why it works:
Intersection is by reference, so if a == b for any nodes a from list A and b from list B, we found the merge point.

Code

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    for (ListNode a = headA; a != null; a = a.next) {
        for (ListNode b = headB; b != null; b = b.next) {
            if (a == b) return a; // found intersection!
        }
    }
    return null; // no intersection
}

Pros: Easy to understand.
Cons: Slow for long lists.

HashSet Approach

Idea:

Traverse list A and store all its nodes in a HashSet.

Traverse list B and check if any node is already in the set.

The first node found in the set is the intersection.

Why it works:
HashSet allows O(1) lookup for each node in list B, so we don’t have to compare every node with every other node.

Code

import java.util.HashSet;

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> visited = new HashSet<>();
        ListNode curr = headA;

        // Store all nodes from list A
        while (curr != null) {
            visited.add(curr);
            curr = curr.next;
        }

        // Traverse list B and check for intersection
        curr = headB;
        while (curr != null) {
            if (visited.contains(curr)) return curr; // intersection found
            curr = curr.next;
        }

        return null; // no intersection
    }
}

Pros: Faster than brute force.
Cons: Uses extra memory (O(N)) for the HashSet.

Two-Pointer Approach (Optimal)

Idea:

Use two pointers pA and pB starting at the heads of each list.

Move one step at a time.

When a pointer reaches the end, redirect it to the head of the other list.

They will eventually meet at the intersection or reach null simultaneously if there’s no intersection.

Why it works:
By switching heads after reaching the end, both pointers travel the same total distance (lenA + lenB), aligning them perfectly at the intersection.

Code:

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode pA = headA;
        ListNode pB = headB;

        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }

        return pA; // intersection node or null
    }
}

Pros: Elegant, no extra memory, fastest in practice.
Cons: Slightly trickier to understand initially.

Summary Table

Approach	Time	Space	Notes
Brute Force	O(N × M)	O(1)	Simple, but slow
HashSet	O(N + M)	O(N)	Fast, uses extra memory
Two Pointer	O(N + M)	O(1)	Elegant and optimal

Wrapping Up

Intersection of two linked lists is a great way to understand pointers, references, and linked list fundamentals.

• Brute force helps you grasp the basics.
• HashSet gives a quick optimization.
• Two-pointer approach is elegant and interview-friendly.

We’d love your support in this beginning!
If you found this helpful, share your thoughts, ask questions, and let’s build a learning community together. Every comment and suggestion helps us grow — and helps others on their coding journey.