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.
|
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 |
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
Intersecting node: 7
That;s all about finding Intersection of two linked lists.
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
