Intersection point of two linked list

Given two singly linked lists of size N and M, write a program to get the point where two linked lists intersect each other, return null if the lists do not intersect.

Example

Input:

List 1 = [1,3,1,2,4], List 2 = [3,2,4]

Output: 2

Approach

The difference between the lengths of the two linked lists can be used to find the intersection of the linked lists.

Let us understand the approach with steps below.

Step 1 : Create two dummy nodes namely d1 and d2 pointing to the head of the first linked list and head of the second linked list respectively.

Step 2 : Traverse both the linked lists using the dummy nodes and calculate the length of the linked list

Step 3 : Calculate the positive difference between the lengths of the two linked lists.

Step 4 : Place the dummy pointers back to the start of the respective linked lists.

Step 5 : Move the dummy pointer of the larger list by the difference achieved. Move both pointers, each pointing two lists, ahead simultaneously if both do not collide.

Step 6 : The node at which the pointers collide is the intersection point of the two linked lists.

Step 7 : The node at which the pointers collide is the intersection point of the two linked lists. If the pointers do not collide then this indicates that there is no intersection present.

Complexity

• Time Complexity: O(2max(length of list1,length of list2))+O(abs(length of list1-length of list2))+O(min(length of list1,length of list2))

• Finding the length of both lists takes max(length of list1, length of list2) because it is found simultaneously for both of them. Moving the head pointer ahead by a difference of them. The next one is for searching.

• Space Complexity: O(1)

Code

# Java Code

import java.util.*;

class LinkedListIntersection {

    static class Node {
        int num;
        Node next;

        Node(int val) {
            num = val;
            next = null;
        }
    }

    // Utility function to insert node at the end of the linked list
    static Node insertNode(Node head, int val) {
        if (head == null) {
            return new Node(val);
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = new Node(val);
        return head;
    }

    // Utility function to print linked list
    static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.num);
            if (current.next != null) {
                System.out.print("->");
            }
            current = current.next;
        }
        System.out.println();
    }

    // Utility function to calculate the difference in lengths of two linked lists
    static int getDifference(Node head1, Node head2) {
        int len1 = 0, len2 = 0;
        Node temp1 = head1, temp2 = head2;

        while (temp1 != null) {
            len1++;
            temp1 = temp1.next;
        }
        while (temp2 != null) {
            len2++;
            temp2 = temp2.next;
        }

        return len1 - len2;
    }

    // Utility function to check presence of intersection
    static Node intersectionPresent(Node head1, Node head2) {
        int diff = getDifference(head1, head2);

        if (diff < 0) {
            while (diff++ != 0) {
                head2 = head2.next;
            }
        } else {
            while (diff-- != 0) {
                head1 = head1.next;
            }
        }

        while (head1 != null && head2 != null) {
            if (head1 == head2) {
                return head1;
            }
            head1 = head1.next;
            head2 = head2.next;
        }

        return null;
    }

    public static void main(String[] args) {
        // Creation of both lists
        Node head1 = null;
        head1 = insertNode(head1, 1);
        head1 = insertNode(head1, 3);
        head1 = insertNode(head1, 1);
        head1 = insertNode(head1, 2);
        head1 = insertNode(head1, 4);

        // Creating second list
        Node head2 = null;
        head2 = insertNode(head2, 3);

        // Creating intersection
        Node intersectNode = head1.next.next.next; // Node with value 2
        head2.next = intersectNode;

        // Printing the lists
        System.out.print("List 1: ");
        printList(head1);

        System.out.print("List 2: ");
        printList(head2);

        // Checking if intersection is present
        Node intersectionNode = intersectionPresent(head1, head2);
        if (intersectionNode == null) {
            System.out.println("No intersection");
        } else {
            System.out.println("The intersection point is " + intersectionNode.num);
        }
    }
}

Output

List 1: 1->3->1->2->4
List 2: 3->2->4
The intersection point is 2