Find the Intersection Node of two Linked Lists

In this article, we will implement the algorithm to find the intersection node of two given linked lists in Java. The intersection node is the common merging node between two given linked lists.

It may happen that 2 linked lists are merged at any common node due to some programming error or to avoid extra memory allocation for millions of common nodes between two linked lists.

For example, given below two different linked lists with some common nodes:

Once both the linked lists are merged then we will have a linked list in below form:

Hence, we need to write an algorithm to find this intersection node between these two linked lists which is actually the node with data 100.

Approach

To find this intersection point I can think of 2 different approaches - one is to traverse both the list with an inner and outer loop and check for any common node. If the outer loop is for the first linked list traversal and the inner loop for second linked list traversal then for each node of the first linked list all the nodes in the second lists need to be compared. This will have a worst-time complexity of O(N x M) where N is the length of the first linked list and M is the length of the second linked list.

The second approach could be traversing each list in a single loop and compare every node of each list. At some point, we will reach the intersection point at once but this will only work for an equal number of nodes present before the intersection point. This will not work for an unequal number of nodes. But we can definitely modify it to make it work.

First, we can find the length of each linked list and find the difference(d). Then we can skip the d number of nodes from the longest list and then traverse each list in a single loop and compare their node value to find the intersection point.

Algorithm to Find Intersection Node

Below is the algorithm for the same.

• Find the length of each linked lists as firstListLength and secondListLength
• If both lengths firstListLength and secondListLength are same then invoke findIntersectionOfEqualSizeList() to find the intersection node.
• Else find the difference in the length as diff and traverse that many nodes in the longest list and use a temp variable to mark the start node of the longest list.
• Invoke findIntersectionOfEqualSizeList() with the smallest list head node and the temp node.

Algorithm Implementation

Below is our linked list node class implementation in Java. The custom implementation of the list in Java can be found here.

public class Node {

    private int data;
    private Node nextNode;

//setters and getters

}

Below is the implementation to find the length of a linked list.

private int findLength(Node head) {
        Node node = head;
        int length = 0;
        while (node != null){
             length = length + 1;
             node = node.getNextNode();

        }
        return length;
    }

Now, let us implement the code that will find the difference in the length of the list and take the decision to skip the traversal of the number of nodes from the longest list.

public Node findIntersection(Node head1, Node head2){
        if (head1 == null || head2 == null){
            return null;
        }
        Node intersectionNode;
        int firstListLength = findLength(head1);
        int secondListLength = findLength(head2);
        if (firstListLength == secondListLength){
            intersectionNode = findIntersectionOfEqualSizeList(head1, head2);
        }else {
            if (firstListLength > secondListLength){
                Node temp = head1;
                int diff = firstListLength - secondListLength;
                while (diff != 0){
                    temp = temp.getNextNode();
                    diff = diff - 1;
                }
                intersectionNode = findIntersectionOfEqualSizeList(temp, head2);
            }else {
                Node temp = head2;
                int diff = secondListLength - firstListLength;
                while (diff != 0){
                    temp = head2.getNextNode();
                    diff = diff - 1;
                }
                intersectionNode = findIntersectionOfEqualSizeList(head1, temp);
            }
        }
        return intersectionNode;
    }
    

Below is the code that actually finds the intersection node. It loops in both the lists and compares each node data to find the intersection.

private Node findIntersectionOfEqualSizeList(Node head1, Node head2){
        Node temp1 = head1;
        Node temp2 = head2;
        while (temp1 != null && temp2 != null){
            if (temp1.getData() == temp2.getData()){
                return temp1;
            }
            temp1 = temp1.getNextNode();
            temp2 = temp2.getNextNode();
        }
        return null;
    }

Runner Class Implmentation

Below is the Runner class that creates linked lists with an intersection node.

public class LinkedListRunner {

    public static void main(String [] args){

        Node commonNodes = null;
        int[] commonData = {80, 90, 100};
        for (int i = 0; i < commonData.length; i++){
            Node node = new Node(commonData[i]);
            node.setNextNode(commonNodes);
            commonNodes = node;
        }

        Node node1 = commonNodes;
        int[] firstListData = {1, 2, 3};
        for (int i = 0; i < firstListData.length; i++){
            Node node = new Node(firstListData[i]);
            node.setNextNode(node1);
            node1 = node;
        }

        Node node2 = commonNodes;
        int[] secondListData = {4, 5};
        for (int i = 0; i < secondListData.length; i++){
            Node node = new Node(secondListData[i]);
            node.setNextNode(node2);
            node2 = node;
        }

        CustomLinkedList customLinkedList1 = new CustomLinkedList();
        Node intersectionNode = customLinkedList1.findIntersection(node1, node2);
        System.out.println(intersectionNode.getData());

    }
}

Conclusion

In this article, we implemented the algorithm to find the intersection node of two given linked lists in Java.