Problem Statement (Asked By Google)

You are given two singly linked lists that intersect at some node. Your task is to find and return the first intersecting node.

• The linked lists are non-cyclical.
• Nodes with the same value in both lists represent the exact same node object.

Example:

Input:

A = 3 -> 7 -> 8 -> 10  
B = 99 -> 1 -> 8 -> 10  

Output:

Node with value 8

Explanation:

• The two lists merge at node 8, so the function should return this node.

Constraints:

• The solution must run in O(M + N) time, where M and N are the lengths of the two lists.
• The algorithm should use constant space (O(1) extra space).

Problem link: https://leetcode.com/problems/intersection-of-two-linked-lists/

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

---

Brute Force Approach: Using HashSet (O(M + N) Time, O(Max(M, N)) Space)

Step-by-Step Explanation

1. Store All Nodes of One List in a HashSet
   • Traverse the first list and store each node reference in a HashSet.
2. Check for Intersection in the Second List
   • Traverse the second list and check if any node exists in the HashSet.
   • The first matching node is the intersection.
3. Why This Works?
   • Since nodes are compared by reference, we can efficiently find the intersection.

Java Code (Brute Force with HashSet)

import java.util.HashSet;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

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

        // Store all nodes of list A in the HashSet
        while (headA != null) {
            visited.add(headA);
            headA = headA.next;
        }

        // Traverse list B and check if any node is already in the HashSet
        while (headB != null) {
            if (visited.contains(headB)) {
                return headB; // Found the intersection node
            }
            headB = headB.next;
        }

        return null; // No intersection found
    }

    public static void main(String[] args) {
        ListNode common = new ListNode(8);
        common.next = new ListNode(10);

        ListNode headA = new ListNode(3);
        headA.next = new ListNode(6);
        headA.next.next = common;

        ListNode headB = new ListNode(5);
        headB.next = common;

        ListNode intersection = getIntersectionNode(headA, headB);
        System.out.println(intersection != null ? "Intersection at: " + intersection.val : "No Intersection");
    }
}

Time and Space Complexity (Brute Force)

• Time Complexity: O(M+N) (traverse both lists once).
• Space Complexity: O(max(M,N)) (store nodes in HashSet).

Optimized Approach: Two Pointers (O(M + N) Time, O(1) Space)

Step-by-Step Explanation

1. Find the Length of Both Lists
   • Compute the length M and N of both linked lists.
2. Align the Pointers
   • Move the pointer of the longer list forward by |M – N| steps.
3. Traverse Both Lists Together
   • Move both pointers one step at a time.
   • The first common node is the intersection.

Java Code (Optimized O(1) Space Solution)

public class IntersectionLinkedListOptimized {
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lengthA = getLength(headA);
        int lengthB = getLength(headB);

        // Align the starting positions
        while (lengthA > lengthB) {
            headA = headA.next;
            lengthA--;
        }
        while (lengthB > lengthA) {
            headB = headB.next;
            lengthB--;
        }

        // Traverse both lists together to find intersection
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }

        return headA; // Either the intersection node or null
    }

    private static int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    public static void main(String[] args) {
        ListNode common = new ListNode(8);
        common.next = new ListNode(10);

        ListNode headA = new ListNode(3);
        headA.next = new ListNode(6);
        headA.next.next = common;

        ListNode headB = new ListNode(5);
        headB.next = common;

        ListNode intersection = getIntersectionNode(headA, headB);
        System.out.println(intersection != null ? "Intersection at: " + intersection.val : "No Intersection");
    }
}

Time and Space Complexity (Optimized)

• Time Complexity: O(M+N) (traverse both lists once).
• Space Complexity: O(1) (constant extra space).

Comparison of Both Approaches

Approach	Time Complexity	Space Complexity	Explanation
Brute Force (HashSet)	O(M+N)	O(max⁡(M,N))	Uses extra space to store visited nodes.
Optimized (Two Pointers)	O(M+N)	O(1)	Uses length difference to align pointers efficiently.

Final Thoughts

• Use the HashSet approach when space isn’t a constraint but you want a quick solution.
• Use the Two Pointers approach for an optimized O(1) space solution.
• Both solutions run in linear time O(M+N). 🚀

---

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.