How to find the joining point of two linked lists?

Problem statement

Given two linked lists, one linked list joins the other linked list at some point. How will you find the joining point of two linked lists?

Illustration

Pseudo code/Solution

Option#1

1. Connect List#1 last node to List#2 first node. It will create a circle in the List.
2. Find out the circle node and you get the “joining node”

Option#2 (Less time complex)

1. Find the difference between the length of the first list and the second list
2. Move the head of the lengthier list to the steps difference found in step#1 above e.g. if the difference is 2 the L1H1 (list1-head1) should be moved to N3 and then start step#3
3. Start moving H1 & H2 till you reach the point where both list nodes become the same
4. The breakpoint node of step#3 is the joining point node.

Java Code

public class TwoLinkedListJoinPoint {

public static void main(String[] args) {
 Linkedlist<Integer> ll1 = new Linkedlist<>();
 Node<Integer> n1 = new Node<>(1);
 Node<Integer> n2 = new Node<>(2);
 Node<Integer> n3 = new Node<>(3);
 Node<Integer> n4 = new Node<>(4);
 Node<Integer> n5 = new Node<>(5);
 Node<Integer> n6 = new Node<>(6);
 Node<Integer> n7 = new Node<>(7);

 ll1.setHead(n1);

 n1.setNext(n2);
 n2.setNext(n3);
 n3.setNext(n4);
 n4.setNext(n5);
 n5.setNext(n6);
 n6.setNext(n7);

 Linkedlist<Integer> ll2 = new Linkedlist<>();
 Node<Integer> n18 = new Node<>(18);
 Node<Integer> n19 = new Node<>(19);

 ll2.setHead(n18);
 n18.setNext(n19);
 n19.setNext(n4);

 System.out.println(joinPoint2(ll1, ll2).getData());
}

private static Node<Integer> joinPoint1(Linkedlist<Integer> ll1, Linkedlist<Integer> ll2) {
Node<Integer> h1 = ll1.getHead();
Node<Integer> h2 = ll2.getHead();
 
 while(h1!=null) {
  while(h2!=null) {
   if(h1 == h2) {
    return h1;
   }
   h2 = h2.getNext();
  }
  h1 = h1.getNext();
  h2 = ll2.getHead();
 }
 // O(n^2)
 return null;
 }

private static Node<Integer> joinPoint2(Linkedlist<Integer> ll1, Linkedlist<Integer> ll2) {
 Node<Integer> h1 = ll1.getHead();
 Node<Integer> h2 = ll2.getHead();

 int count1 = 0;
 int count2 = 0;

 while(h1 != null) {
  h1 = h1.getNext();
  count1++;
 } //10

 while(h2 != null) {
  h2 = h2.getNext();
  count2++;
 }//10

 if (count1 > count2) {
  int diff = count1 - count2;
  h1 = ll1.getHead();
  while(diff > 0) {
   h1 = h1.getNext();
   diff--;
  }
 }//10
 h2 = ll2.getHead();
 while(h2 != null) {
  if(h1 == h2) {
  return h1;
 }
 h1 = h1.getNext();
 h2 = h2.getNext();
 }//10
 return null;
 }
}

Feel free to share your viewpoints on this topic in the comments section below 🙂

Spread the word!