Intersection

Given two (singly) linked lists, determine if the two lists intersect. Return the inter-secting node.

Note that the intersection is defined based on reference, not value. That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting.

👉 Link here to the repo to solve the problem

👌 Tips

You can do this in 0 (A+B) time and 0 (1) additional space. That is, you do not need a hash table (although you could do it with one).

Examples will help you. Draw a picture of intersecting linked lists and two equivalent linked lists (by value) that do not intersect.

Focus first on just identifying if there's an intersection.

Observe that two intersecting linked lists will always have the same last node. Once they intersect, all the nodes after that will be equal.

You can determine if two linked lists intersect by traversing to the end of each and comparing their tails.

Now, you need to find where the linked lists intersect. Suppose the linked lists were the same length. How could you do this?

If the two linked lists were the same length, you could traverse forward in each until you found an element in common. Now, how do you adjust this for lists of different lengths?

Try using the difference between the lengths of the two linked lists.

If you move a pointer in the longer linked list forward by the difference in lengths, you can then apply a similar approach to the scenario when the linked lists are equal.

👊 Solution 1

This is a simple hashmap solutions that is in O(N + M) as we have to traverse both lists, the first time around adding each hashcode of each object to a HashSet. This in order to know if we are referencing the same object.

When we do the checks on the second list, if one of the elements is in the HashSet we can just return the element, else return null.

public static SingleLinkedListNode linkedListIntersectionHashMap(SingleLinkedListNode node1, SingleLinkedListNode node2) {
        HashSet<Integer> hash = new HashSet<>();

        while (node1.next != null) {
            hash.add(node1.hashCode());
            node1 = node1.next;
        }
        
        while (node2.next != null) {
            if (hash.contains(node2.hashCode())) return node2;
            node2 = node2.next;
        }

        return null;
    }

👊 Solution 2

In this approach I could implenent a solution which would require less space and the same runtime O(N+M). I could do this if I can get the length of both lists and move the node which has the longest length by a by the difference between the shortest list and the length of the longest.

if the last node of each list is different we already know the lists have diverged and there is no intersecting node.

From then is just a matter of iterating through the lists until both hashCodes match.

    public static SingleLinkedListNode linkedListIntersectionTailCheck(SingleLinkedListNode node1, SingleLinkedListNode node2) {

        SingleLinkedListNode lastNode1 = getLastNode(node1);
        SingleLinkedListNode lastNode2 = getLastNode(node2);
        if (lastNode1.hashCode() != lastNode2.hashCode()) return null;

        int n1Length = node1.length();
        int n2Length = node2.length();

        if (n1Length > n2Length) {
            for (int i = 0; i < n1Length - n2Length; i++) {
                node1 = node1.next;
            }
        } else {
            for (int i = 0; i < n2Length -  n1Length; i++) {
                node2 = node2.next;
            }
        }

        while (node1.next != null && node2.next != null) {
            if (node1.hashCode() == node2.hashCode()) return node1;
            node1 = node1.next;
            node2 = node2.next;
        }
        return  null;
    }

---

Question borrowed from “Cracking the coding interview”