In this post, we will talk and learn How to find Intersection of two linked lists.
Let’s say there are two singly LinkedList’s because of some programming error, the end node of one of the LinkedList got linked to the second LinkedList and formed a Y shaped list. We have to write a program to get the point where these two LinkedList’s merge
For example, the following two linked lists:
This diagram shows an example with two linked lists having 30 as intersection points.
The Logic used in this Program:
Here is the very simple Logic to find Intersection of two linked lists.
- First of all, find the length of both singly-linked lists.
- Afterward, we find the bigger linked list and iterate up to the difference between two linked lists.
- You should note that two linked lists will become equal at this step.
- Iterate over both the linked lists and keep checking if there is any common node present if we find one then return that Node else return null
Below is the complete source code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
package com.kkjavatutorials.util; /** * How to find intersection of two LinkedList ? * @author KK JavaTutorials */ public class LinkedList<T> { private Node<T> head; //This internal class represents Node in Linked List private static class Node<T>{ private T data; private Node<T> next; public Node(T data) { super(); this.data = data; this.next = null; } } /** * This method insert a Node in Linked List * @param newNode has to insert in the List */ public void insert(Node<T> newNode) { if(head == null) { head = newNode; }else { Node<T> currentNode = head; while (currentNode.next != null) { currentNode = currentNode.next; } currentNode.next = newNode; } } /** * Method which traverse Linked List and display all data. */ public void displayLinkedList() { Node<T> currentNode = head; while(currentNode!= null) { System.out.print(currentNode.data+" "); currentNode = currentNode.next; } } /** * @param linkedList1 first LinkedList * @param linkedList2 Second LinkedList * @return Intersection Node of two LinkedLists */ public Node<T> findIntersectionNode(Node<T> linkedList1, Node<T> linkedList2) { int lengthOfList1 = 0; int lengthOfList2 = 0; Node<T> tempLinkedList1 = linkedList1; Node<T> tempLinkedList2 = linkedList2; if (tempLinkedList1 == null || tempLinkedList2 == null) return null; //Finding the length of both linked lists while(tempLinkedList1 != null){ lengthOfList1++; tempLinkedList1 = tempLinkedList1.next; } while(tempLinkedList2 !=null){ lengthOfList2++; tempLinkedList2 = tempLinkedList2.next; } int difference = 0; Node<T> reference1=linkedList1; Node<T> reference2=linkedList2; //Finding the bigger LinkedList and iterate till the different between two LinkedLists. if(lengthOfList1 > lengthOfList2){ difference = lengthOfList1-lengthOfList2; int i=0; while(i<difference){ reference1 = reference1.next; i++; } }else{ difference = lengthOfList2-lengthOfList1; int i=0; while(i<difference){ reference2 = reference2.next; i++; } } //Now iterate over both the LinkedList and find the common node while(reference1 != null && reference2 != null){ if(reference1 == reference2){ return reference1; } reference1 = reference1.next; reference2 = reference2.next; } return null; } public static void main(String[] args) { LinkedList<Integer> linkedList1 = new LinkedList<>(); Node<Integer> head1 = new Node<Integer>(10); linkedList1.insert(head1); linkedList1.insert(new Node<Integer>(20)); Node<Integer> node = new Node<Integer>(30); linkedList1.insert(node); linkedList1.insert(new Node<Integer>(40)); linkedList1.insert(new Node<Integer>(50)); LinkedList<Integer> linkedList2 = new LinkedList<>(); Node<Integer> head2 = new Node<Integer>(25); linkedList2.insert(head2); linkedList2.insert(node); System.out.println("First LinkedList::"); linkedList1.displayLinkedList(); System.out.println(); System.out.println("Second LinkedList::"); linkedList2.displayLinkedList(); System.out.println(); Node<Integer> findIntersectionNode = linkedList1.findIntersectionNode(head1, head2); if(findIntersectionNode==null){ System.out.println("Therse two linked lists do not intersection Node!!"); } else { System.out.println("Intersecting node is: "+findIntersectionNode.data); } } } |
Output of this Program:
First LinkedList::
10 20 30 40 50
Second LinkedList::
25 30 40 50
Intersecting node is: 30
You May Also Like:
- How to convert sorted Linked List to balanced Binary Search Tree?
- How to check if LinkedList is palindrome or not in java ?
- Find start node of loop in Singly LinkedList in java?
- Implementation to reverse a Singly Linked List in Java ?
- Implementing a Circular Singly Linked List in Java ?
- How to remove a given key from the Singly Linked List in Java ?
- How to remove a node from a Singly Linked List at a given position in Java?
That’s all about How to find the intersection of two LinkedList in java?
If you have any feedback or suggestion please feel free to drop in below comment box.