Intersection of two linked lists

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

In this post, we will see how to find Intersection of two linked lists.

Problem

Given two singly linked lists, find if two linked lists intersect. If they intersect, find intersection point.

Solution

Here is simple algorithm to find Intersection of two linked lists.

• Find the length of both singly linked lists.
• Find the bigger linked list and iterate up to the difference between two linked list.
• Please note that two linked list will become equal at this step.
• Iterate over both linked list and check if there is any common node, if you find one, return it.
• Else return null.

package org.arpit.java2blog;

public class LinkedList{

    private Node head;

    private static class Node {
        private int value;
        private Node next;

        Node(int value) {
            this.value = value;

        }
    }

    public void addToTheLast(Node node) {

        if (head == null) {
            head = node;
        } else {
            Node temp = head;
            while (temp.next != null)
                temp = temp.next;

            temp.next = node;
        }
    }

    public Node findIntersectionNode(Node list1, Node list2) {
        int lengthOfList1 = 0;
        int lengthOfList2 = 0;
        Node temp1=list1, temp2=list2;
        if (temp1 == null || temp2 == null)
            return null;

        // Find the length of both linked list
        while(temp1 != null){
            lengthOfList1++;
            temp1 = temp1.next;
        }
        while(temp2 !=null){
            lengthOfList2++;
            temp2 = temp2.next;
        }

        int difference = 0;
        Node ptr1=list1;
        Node ptr2=list2;

        // Find bigger linked list and iterate upto the different between two linked list.
        if(lengthOfList1 > lengthOfList2){
            difference = lengthOfList1-lengthOfList2;
            int i=0;
            while(i<difference){
                ptr1 = ptr1.next;
                i++;
            }
        }else{
            difference = lengthOfList2-lengthOfList1;
            int i=0;
            while(i<difference){
                ptr2 = ptr2.next;
                i++;
            }
        }

        // Iterate over both linked list and find the common node
        while(ptr1 != null && ptr2 != null){
            if(ptr1 == ptr2){
                return ptr1;
            }
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }

        return null;
    }

    public static void main(String[] args) {
        LinkedList list1 = new LinkedList();
        // Creating a linked list
        Node head1=new Node(5);
        list1.addToTheLast(head1);
        list1.addToTheLast(new Node(6));
        Node node = new Node(7);
        list1.addToTheLast(node);
        list1.addToTheLast(new Node(1));
        list1.addToTheLast(new Node(2));

        LinkedList list2 = new LinkedList();
        Node head2=new Node(4);
        list2.addToTheLast(head2);
        list2.addToTheLast(node);

        Node findIntersectionNode = list1.findIntersectionNode(head1, head2);
        if(findIntersectionNode==null)
        {
            System.out.println("Two linked lists do not intersect!!");
        }
        else
        {
            System.out.println("Intersecting node: "+findIntersectionNode.value);
        }
    }

}

When you run above program, you will get below output

That;s all about finding Intersection of two linked lists.