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 110 |
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.