Intersection Point of two Linked Lists

The problem, simply

You get the heads of two singly linked lists. At some box they may join, and from there on they share the very same boxes until the end, like the letter Y. Find the first shared box. If they never join, return null.

Shared means the same box in memory, not just the same number. Two different boxes that both hold 7 are not a meeting point. You may not change the lists, and there are no loops.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk list A and drop every box into a bag, a hash set of boxes. Then walk list B. The first box of B that is already in the bag is where they join.

1. Put every box of A into the set.
2. Walk B. Return the first box that is in the set.
3. If B ends, return null.

class Solution {
    Node intersectPoint(Node head1, Node head2) {
        Set<Node> seen = new HashSet<>();                 // boxes, not numbers
        for (Node p = head1; p != null; p = p.next) seen.add(p);
        for (Node p = head2; p != null; p = p.next) {
            if (seen.contains(p)) return p;               // first shared box
        }
        return null;
    }
}

How long it takes: one walk over each list, O(m + n). Extra room: the bag holds all of A, O(m).

Way 2: the clever way

Use the playground trick. Two fingers walk one step at a time. When a finger runs off the end of its list, it jumps to the head of the other list. Each finger walks A's own part, the shared part, and B's own part, just in a different order, so they line up and land on the meeting box at the same time.

1. pA starts at head A, pB at head B.
2. While pA != pB: move each finger one step. A finger that is on null jumps to the other list's head instead.
3. Return pA. If the lists never join, both fingers reach null together after m + n steps, and null is the right answer.

class Solution {
    Node intersectPoint(Node head1, Node head2) {
        Node pA = head1, pB = head2;
        while (pA != pB) {
            pA = (pA == null) ? head2 : pA.next;   // ran out, take the other street
            pB = (pB == null) ? head1 : pB.next;
        }
        return pA;                                 // the gate, or null if there is none
    }
}

How long it takes: each finger walks at most m + n + 1 steps, O(m + n). Extra room: two fingers, O(1).

Another way: line them up by length

Some interviewers prefer this version because it is easy to prove. Count both lists. Move the finger on the longer list ahead by the difference. Now both fingers are the same distance from the end, so they are also the same distance from the join. Walk them together until they are on the same box.

class Solution {
    Node intersectPoint(Node head1, Node head2) {
        int m = length(head1), n = length(head2);
        Node pA = head1, pB = head2;
        for (int i = 0; i < m - n; i++) pA = pA.next;   // give the longer list a head start
        for (int i = 0; i < n - m; i++) pB = pB.next;
        while (pA != pB) {                              // same distance to the end now
            pA = pA.next;
            pB = pB.next;
        }
        return pA;
    }

    private int length(Node p) {
        int len = 0;
        for (; p != null; p = p.next) len++;
        return len;
    }
}

This is also O(m + n) time and O(1) room. Both ways do about the same amount of walking, so pick the one you can explain best.

Watch out for

• Jumping too early. The finger must step onto null first and jump on the next step, as in the code. If you jump straight from the last box to the other head, two lists with no join never both become null at once, and the loop never ends.
• Changing the lists, for example reversing one or marking boxes. The problem says to keep them as they are.
• Lists with loops. This trick assumes both lists end in null. With loops you first need cycle detection.

What interviewers ask next

• Why do they meet? pA walks a + c + b steps and pB walks b + c + a, where a and b are the private parts and c the shared part. Equal totals, so they arrive at the start of c together.
• Do the two lists share a box at all? Walk both to their last boxes and compare. Same last box means they join somewhere.
• What if the lists might have loops? Find each list's loop start with Floyd's method. If one has a loop and the other does not, they cannot share boxes. If both do, they share boxes only if one loop start is reachable from the other.
• Lowest common ancestor in a tree where every node knows its parent (LeetCode 1650). The path from each node up to the root is a linked list, so the same switching trick finds where the two paths join.

Remember this

Grown-up words: the Y shape is two lists that share a tail, the gate is the intersection node, the bag is a hash set of node references, and switching streets is the two pointer switch technique.