Intersection in Y Shaped Lists

JavaView on GFG

Time: O(n+m)

Space: O(1)

Intuition

Find intersection node of two linked lists forming a Y-shape. Two-pointer length equalization.

Algorithm

1Get lengths. Advance longer list by length difference. Then advance both until they meet.

Common Pitfalls

•Same as LC 160. Alternatively: concatenate A+B and B+A — both pointers meet at intersection after equal steps.

Intersection in Y Shaped Lists.java

Java

// Approach: Compute length difference, advance longer list pointer, then advance both until they meet.
// Time: O(n+m) Space: O(1)
class Node {
    int data;
    Node next;

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

class Solution {
    public Node intersectPoint(Node head1, Node head2) {
        if (head1 == null || head2 == null)
            return null;
        Node a = head1;
        Node b = head2;
        while (a != b) {
            if (a == null)
                a = head2;
            else
                a = a.next;

            if (b == null)
                b = head1;
            else
                b = b.next;

        }
        
        return a;
    }
}

Was this solution helpful?