Write a function to check if 2 LinkedList intersecting each other ?

Suppose there are two singly linked list both of which intersect at some point and become a single linked list. The head and start pointers of both the lists are known, but the intersecting point is not known. Also, the number of nodes in each of the list before they intersect is not known and may be different in each list. Consider list1 may have n nodes before it reaches the intersection point, and list2 might have m nodes before it reaches the intersection point. Where m and n may follow the following rules : m = n , m < n or m > n. Following figure is showing such 2 list which are intersecting in some point.

 

The problem can be solved using a HashSet, which contains the seen nodes in a linked list. In this algorithm we need to follow these steps:

  1. Select a list which has less number of nodes. If we do not know the length, then we can calculate the length of both the Lists.
  2. Traverse the smaller list and add all the nodes in a HashSet named as Seen. Basically these are the visited nodes, which we will try to find in the longer list.
  3. Now traverse the longer list and for each node check, whether the node is present in the Seen HashSet or not. If the node is found in the Seen  HashSet, then it is the intersection point itself.

Consider the following LinkedList ADT which we are going to use for this solution :

package com.algo.linkedlist;

public class Node {

 int data;
 Node next;

 public Node(int data) {
  this.data = data;
  this.next = null;
 }

 @Override
 public boolean equals(Object o) {
  if (this == o) return true;
  if (o == null || getClass() != o.getClass()) return false;
  Node node = (Node) o;
  return data == node.data && next == node.next;
 }

 public void print() {
  System.out.print(this.data);
 }

 public void printCharValue() {
  System.out.print((char) this.data);
 }
}

Following is the LinkedList.java class for creating a LinkedList of specific size.

package com.algo.linkedlist;

public class LinkedList {

 Node head;

 /**
  * Create a Singly LinkedList of given size
  * @param size Size of the LinkedList
  */

 public LinkedList(int size) {
  head = new Node(1);
  Node tempNode = head;
  for (int i = 2; i <= size; i++) {
   Node node = new Node(i);
   tempNode.next = node;
   tempNode = tempNode.next;
  }
 }

/**
  * Create a LinkedList from a String
  * @param str str is the Content of the linked list
  */
 public LinkedList(String str) {
  char[] charArray = str.toCharArray();
  head = new Node(charArray[0]);
  Node tempNode = head;
  for (int i = 1; i < charArray.length; i++) {
   Node node = new Node(charArray[i]);
   tempNode.next = node;
   tempNode = tempNode.next;
  }
 }
}

We are also going to use a Utility method, which can merge 2 linked list and create a intersection point for testing the implementation of both the solution described here:

 /**
  * Merge two linked list in a given position. head1 is pointing
  * to the longer linked list where head2 is pointing to the
  * shorter linked list. Now this method will merge the smaller
  * linked list to the longer one in the given position, after
  * the intersection both forward towards end together.
  *
  */
 public static void mergeLinkedList(Node head1, Node head2, int position) {
  Node temp = head1;
  for (int i = 1; i <= position - 1; i++) {
   temp = temp.next;
  }
  Node temp2 = head2;
  while (temp2 != null) {
   if (temp2.next == null) {
    temp2.next = temp;
    break;
   }
   temp2 = temp2.next;
  }
 }

Now let us implement the above algorithm.

public boolean bySeenMethod(Node head1, Node head2) {
 if (head1 == null || head2 == null) {
  return false;
 }

 // Find the shorter linked list
 boolean result = false;
 Node shorterOne, longerOne = null;
 int len1 = ListUtil.length(head1);
 int len2 = ListUtil.length(head2);
 shorterOne = len1 > len2 ? head2 : head1;
 longerOne = shorterOne == head1 ? head2 : head1;

 Set < Node > seen = new HashSet < > ();
 while (shorterOne != null) {
  seen.add(shorterOne);
  shorterOne = shorterOne.next;
 }

 while (longerOne != null) {
  if (seen.contains(longerOne)) {
   System.out.println("Both the LinkedList are intersected at position " +
    "where the node value is : " + longerOne.data);
   result = true;
   break;
  }
  longerOne = longerOne.next;
 }
 return result;
}

Can we solve the problem in more efficient manner? Yes, the problem can be solved without using extra space or the HashSet. Consider the following algorithm for the same:

  1. Find length L1 and L2 of both the List.
  2. Take the difference between the longer and the smaller list.
  3. Make d number of moves in the longer list. Now both the List has same number of elements.
  4. Make a forward move at a time in both the list, until there is a match in the next pointer of both the list, or one list reaches null. If we can find a match then that is the intersection point of both the list or if we reaches null , then there is no intersection point.
  5. Total time complexity is O(n) and space complexity is O(1).
  6. Consider the following implementation of the algorithm:
public boolean check(Node head1, Node head2) {
 if (head1 == null || head2 == null) {
  return false;
 }
 boolean result = false;
 Node shorterOne = null, longerOne = null;
 int len1 = ListUtil.length(head1);
 int len2 = ListUtil.length(head2);
 if (len1 > len2) {
  longerOne = head1;
  shorterOne = head2;
 } else {
  longerOne = head2;
  shorterOne = head1;
 }

 int difference = len1 > len2 ? (len1 - len2) : (len2 - len1);
 for (int i = 0; i < difference; i++) {
  if (longerOne != null) {
   longerOne = longerOne.next;
  }
 }

 while (longerOne != null || shorterOne != null) {
  if (longerOne.equals(shorterOne)) {
   result = true;
   break;
  }
  longerOne = longerOne.next;
  shorterOne = shorterOne.next;
 }
 return result;
}

Both the implementation can be tested by the following code:

private static void testLinkedListIntersection() {
        LinkedList linkedList = new LinkedList(10);
        LinkedList linkedList1 = new LinkedList(5);
        System.out.println("List 1 before merging: ");
        ListUtil.printList(linkedList.head);
        lineBreak();
        System.out.println("List 2 before merging: ");
        ListUtil.printList(linkedList1.head);
        lineBreak();
        ListUtil.mergeLinkedList(linkedList.head, linkedList1.head, 4);
        lineBreak();
        System.out.println("List 2 after merging: ");
        ListUtil.printList(linkedList1.head);
        lineBreak();
        CheckIntersection checkIntersection = new CheckIntersection();
        System.out.println("If both the list intersect bySeenMethod : "
                + checkIntersection.bySeenMethod(linkedList.head, linkedList1.head));
        System.out.println("If both the list intersect check : "
                + checkIntersection.check(linkedList.head, linkedList1.head));
    }

To test this implementation or for other LinkedList algorithms download the source code from here

core java 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself