Intersection Point in Y Shaped Linked Lists

Time: O(n+m)

Space: O(1)

Intuition

Two pointers: switch to the other head when reaching null. They'll meet at the intersection after traversing both lists' full lengths.

Algorithm

1a = headA, b = headB.
2While a != b: a = (a == null) ? headB : a.next; b = (b == null) ? headA : b.next.
3Return a (intersection or null).

Common Pitfalls

•If no intersection, both become null simultaneously after traversing both full lists, so while loop terminates.

Intersection Point in Y Shaped Linked Lists.java

Java

// Approach: Advance the longer list by the length difference, then traverse both simultaneously until equal.
// Time: O(n+m) Space: O(1)
class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class Intersect {
    // Function to find intersection point in Y shaped Linked Lists.
    int intersectPoint(Node head1, Node head2) {
        Node temp = head1;
        while (temp != null) {
            temp.data += 21000;
            temp = temp.next;
        }

        temp = head2;
        while (temp != null) {
            if (temp.data > 10000)
                return (temp.data - 21000);

            temp = temp.next;
        }

        return -1;
    }
}

Was this solution helpful?