Find intersection point of Y LinkedList

Dec 18, 2024 • 4 mins read

Dhaval Trivedi

Co-founder, Airtribe

Problem Overview

The problem requires us to determine the intersection node of two singly linked lists. Two linked lists intersect if they share some nodes. The task is to write a function that identifies this intersection node, if it exists, and returns it. If the linked lists do not intersect, the function should return null or nullptr.

Understanding the Problem

In the context of linked lists, an intersection occurs when two separate linked lists converge into a single linked list. This means that if a node is shared by both lists, any node following it must also be shared because linked lists do not allow for subsequent branching like trees.

Considerations:

Intersection is defined by reference, not by value. Two nodes are considered the same if they occupy the same memory location.
The node can be any arbitrary node present in both lists, and lists continue to share nodes subsequently from the point of intersection.

Key DSA Concepts and Theory

Linked Lists

Singly Linked List: A data structure consisting of nodes where each node contains data and a reference to the next node in the sequence.

Node Reference vs. Data Value

Reference: Two nodes are equal if their memory addresses are the same.
Data Value: Completely irrelevant in this context, as two nodes may have identical data values yet reside at different addresses.

Intersection Point

When two linked lists start to share nodes, their structural paths merge. The intersection point is the first node that both lists reference simultaneously.

Solution Approach

To solve the problem of finding the intersection of two linked lists, we should adopt an algorithm that traverses both lists. Here's a step-by-step breakdown:

Algorithm Steps:

Calculate Lengths: Determine the lengths of each linked list.
Equalize Starting Point: Advance the pointer of the longer list by the difference in lengths. This ensures both pointers have an equal number of nodes to traverse to reach the end.
Simultaneous Traversal: Traverse both lists concurrently, comparing nodes at each step.
Identify Intersection: If a node reference matches, this node is the intersection; return it.
End: If no intersection exists by the end of both lists, return null.

C++ Implementation:

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    if (!headA || !headB) return nullptr;
    
    ListNode* currentA = headA;
    ListNode* currentB = headB;
    
    while (currentA != currentB) {
        currentA = currentA ? currentA->next : headB;
        currentB = currentB ? currentB->next : headA;
    }
    
    return currentA;
}

Java Implementation:

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

        ListNode currentA = headA;
        ListNode currentB = headB;

        while (currentA != currentB) {
            currentA = (currentA != null) ? currentA.next : headB;
            currentB = (currentB != null) ? currentB.next : headA;
        }

        return currentA;
    }
}

Time and Space Complexity Analysis

Time Complexity: O(n + m), where n and m are the lengths of the two lists. Each node is potentially visited twice.
Space Complexity: O(1) as no additional space is used apart from the input variables.

Common Mistakes to Avoid

Confusing Value Equality with Reference Equality: The intersection is determined by reference, meaning the same node in memory, not merely nodes containing the same value.
Boundary Condition Checks: Failing to address the scenario where one or both heads are null.

Additional Resources and References

This article aims to provide a detailed exploration of the intersection of two linked lists. By understanding the theoretical basis and carefully implementing the solution, one can seamlessly navigate the problem and apply these concepts to similar challenges.