Wednesday, May 4, 2022

Question 53 : Find intersection of two linked lists?

Given two singly linked lists, find if two linked lists intersect. If they intersect, find the intersection point.

Solution

Here is a simple algorithm to find the 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 the two linked lists.
• Please note that two linked lists will become equal at this step.
• Iterate over both linked lists and check if there is any common node, if you find one, return it.
``````public class LinkedList{

private static class Node {
private int value;
private Node next;

Node(int value) {
this.value = value;

}
}

} else {
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) {
Node node = new Node(7);

if(findIntersectionNode==null)
{
System.out.println("Two linked lists do not intersect!!");
}
else
{
System.out.println("Intersecting node: "+findIntersectionNode.value);
}
}

}
``````
When you run the above program, you will get below output
``Intersecting node: 7``

Don't miss the next article!
Be the first to be notified when a new article or Kubernetes experiment is published.