Intersection of two Sorted Linked List

The problem, simply

You get two linked lists, each sorted from small to big. Build a new list with the numbers that are in both lists, also sorted. Do not change the two input lists: the answer must be made of new boxes.

If a number repeats, each box can be matched only once. So 1 1 2 and 1 1 1 share two 1s. Some versions want each common number only once; that is a one line change, shown below.

A story to remember it

Picture it

Examples

Way 1: the simple way

Forget that the lists are sorted. Count what is in b, then walk a and take what is still available.

1. Walk b and count each number in a map.
2. Walk a. If the count of the number is more than 0, add a new box with it to the answer and lower the count.

class Solution {
    public static Node findIntersection(Node head1, Node head2) {
        Map<Integer, Integer> count = new HashMap<>();
        for (Node p = head2; p != null; p = p.next) count.merge(p.data, 1, Integer::sum);

        Node dummy = new Node(0), tail = dummy;
        for (Node p = head1; p != null; p = p.next) {
            int c = count.getOrDefault(p.data, 0);
            if (c > 0) {
                tail.next = new Node(p.data);   // a new box, inputs stay untouched
                tail = tail.next;
                count.put(p.data, c - 1);       // each box of b is used once
            }
        }
        return dummy.next;
    }
}

How long it takes: one walk over each list, O(m + n). Extra room: the map can hold every number of b, O(n). It works even for unsorted lists, but it wastes the sorted order.

Way 2: the clever way

Use the sticker album trick with two pointers. The sorted order tells us which finger can safely move.

1. Make a dummy box and a tail finger on it. New boxes hang after tail.
2. While both a and b are on a box: if a.data == b.data, hang a new box with that number and move a, b and tail.
3. If a.data < b.data, move a. Otherwise move b.
4. Return dummy.next.

class Solution {
    public static Node findIntersection(Node head1, Node head2) {
        Node dummy = new Node(0), tail = dummy;   // dummy saves a special case for the first box
        Node a = head1, b = head2;
        while (a != null && b != null) {
            if (a.data == b.data) {
                tail.next = new Node(a.data);
                tail = tail.next;
                a = a.next;
                b = b.next;
            } else if (a.data < b.data) {
                a = a.next;                       // a is too small to ever match
            } else {
                b = b.next;                       // b is too small to ever match
            }
        }
        return dummy.next;
    }
}

For distinct values only, change the match line to add the box only when tail == dummy || tail.data != a.data.

How long it takes: each step moves at least one finger, so at most m + n steps, O(m + n). Extra room: a few fingers, O(1), not counting the answer list that we must build anyway.

Watch out for

• Moving only one finger after a match. Then the same box gets matched again and you get extra copies.
• Stopping too late. As soon as either list ends, nothing more can match.
• Forgetting to ask about repeats. Matching each box once and listing each value once give different answers on 1 1 3.
• Returning dummy instead of dummy.next.

What interviewers ask next

• Union of two sorted lists. Same walk, but take the smaller value each step and take both tails at the end. That is the merge step of merge sort.
• The lists are not sorted. Use Way 1 with a hash map, or sort both with merge sort first, O(n log n).
• One list is much longer than the other. Walk the short list and binary search in the long one. With an array that is O(m log n), but a linked list has no random access, so the two pointers are still best.
• Intersect k sorted lists. Intersect them two at a time, smallest first, so the answer shrinks quickly.
• Intersection point of two lists that share boxes. That is a different problem: it is about the same box, not the same number.

Remember this

Grown-up words: the sticker albums are sorted linked lists, the fingers are two pointers, the dummy box is a sentinel node, tail is the tail pointer of the answer, and matching each box once is a multiset intersection.