Linked List: Program to find the intersection of two linked list

Write a program to find the intersecting node if its exists for two given linked list

For finding intersecting node of two linked lists, we use the following approach

• The basic idea is to push all nodes of two linked lists into two different stacks
• Then pop elements from each stack simultaneously and check whether they are the same
• When the elements are not same, the previous element is the intersection point
• In order to access the previous element, we store it inside a temp variable

Algorithm

1. Create two pointers, say current1 and current2, and point on the respective head node of two linked lists
2. Create two stack named stack1 and stack2
3. Push all nodes of linked list 1 and 2 into stack1 and stack2 respectively
4. While the peek node of both stacks is the same
   • store the top element of stack in temp and then pop element from both stack
5. When the loop breaks, we have passed the intersecting node which we have stored in temp, so print temp.data

Complexity

Time Complexity : Time Complexity : O(m+n) , where m and n are length of respective linked list
Space Complexity : Space Complexity : O(m+n), where m and n are length of respective linked list

Java Code

import java.util.*;

class LinkedListFindIntersection{

	class Node {
	    // initialising data field and next pointer of node
	    int data;
	    Node next;
	 
	    Node(int d) {
	        this.data = d;
	        this.next = null;
	    }
	}
 
    Node head;
 
    // creating a linked list using array
    public void buildLinkedlist(int A[], int noOfNodes) {
        int i;
        Node temp, last;
        temp = new Node(A[0]);
        temp.next = null;
        this.head = temp;
        last = temp;
        for (i = 1; i < noOfNodes; i++) {
            // System.out.println(head.data);
            temp = new Node(A[i]);
            temp.next = null;
            last.next = temp;
            last = temp;
        }
    }
 
    // printing of linkedList
    public void printLinkedlist() {
        List<String> allNodesList = new ArrayList<>();
        Node temp = this.head;
        while (temp != null) {
            allNodesList.add(Integer.toString(temp.data));
            temp = temp.next;
        }
        System.out.println(String.join(" -> ", allNodesList));
    }
 
    public static void findIntersection(Node head1, Node head2) {
        Stack<Node> stack1 = new Stack<Node>();
        Stack<Node> stack2 = new Stack<Node>();
        Node current1 = head1;
        Node current2 = head2;
        while (current1 != null) {
            stack1.push(current1);
            current1 = current1.next;
        }
        while (current2 != null) {
            stack2.push(current2);
            current2 = current2.next;
        }
        Node temp = null;
        while (stack1.peek() == stack2.peek()) {
            temp = stack1.peek();
            stack1.pop();
            stack2.pop();
        }
        System.out.println("Intersecting node of two given linked list is : " + temp.data);
 
    }
 
    public static void main(String[] args) {
        int[] linkedlistElements1 = new int[] { 5, 6, 7, 1, 2 };
        int numberOfNodes1 = 5;
        int[] linkedlistElements2 = new int[] { 4, 7, 1, 2 };
        int numberOfNodes2 = 4;
       
        // initialising object of linkedlist class
        LinkedListFindIntersection ll1 = new LinkedListFindIntersection();
        LinkedListFindIntersection ll2 = new LinkedListFindIntersection();
 
        ll1.buildLinkedlist(linkedlistElements1, numberOfNodes1);
        System.out.println("Given Linked List 1 ");
        ll1.printLinkedlist();

        ll2.buildLinkedlist(linkedlistElements2, numberOfNodes2);
        System.out.println("Given Linked List 2 ");
        ll2.printLinkedlist();

        // Create intersection
        ll2.head.next = ll1.head.next.next;
        
        LinkedListFindIntersection.findIntersection(ll1.head, ll2.head);
 
    }

}

Output

Given Linked List 1 
5 -> 6 -> 7 -> 1 -> 2
Given Linked List 2 
4 -> 7 -> 1 -> 2
Intersecting node of two given linked list is : 7