Algorithm gymnastics 12

Intersection Point of Two Lists

Description

The heads of the two Linked Lists are passed, so find out if the two Linked Lists actually intersect, Let's implement an algorithm that returns that intersection. Returns null if there are no intersections. Being an intersection means that Nodes have the same memory address.

In the example below, neither list intersects. In the following example, there is a node that holds 12 data at the intersection, so that node is returned.

Solution1 First of all, the first implementation method that comes to mind is whether the node of the first Linked List also exists in the second Linked List. An inefficient algorithm with an execution time of O (m * n) (m and n are the lengths of the Linked List). In this case, the execution time is slow, but Space Complexity is O (1) because it only scans using two pointers.

Solution2 But let's say you have plenty of memory and want to improve your execution time more efficiently. In that case, the first thing that comes to mind is It is to use a data structure that uses HashTable. Therefore, we will implement it using Java's HashSet. First, add Nodes to HashSet while linearly scanning the elements of one Linked List. After that, check if the same Node exists in the HashSet while linearly scanning the second Linked List. Since the access to the elements of HashSet is of course O (1), the execution time of this implementation is O (m + n), which is more efficient.

Implementation

Intersect.java

class Intersect{
  public LinkedListNode findintersect(LinkedListNode head1,LinkedListNode head2) {

    LinkedListNode cur1 = head1;
    LinkedListNode cur2 = head2;
    LinkedListNode interSectionNode = null;
    HashSet<LinkedListNode> hashSet = new HashSet<>();

    while (cur1 != null) {
      hashSet.add(cur1);
      cur1 = cur1.next;
    }

    while (cur2 != null) {
      if (hashSet.contains(cur2)) {
        interSectionNode = cur2;
        break;
      }
      cur2 = cur2.next;
    }

    return interSectionNode;
  } 
}

Solution3 Now, let's assume that there is a huge amount of data in the Linked List and consider whether we can improve the memory efficiency a little more. First, let's assume that both Linked Lists are the same size. In this case, you can compare the Node's addresses using two different pointers from the beginning of both. If these addresses match, it means that it is an intersection. If they do not match, advance both pointers ** simultaneously ** by one to compare the addresses. Repeat this process until you find an intersection or both lists are gone. Now, if the list lengths are different, let's use this concept for the problem.

1. Find the lengths of both Linked Lists: L1 and L2. 2.Calculate the difference in length between L1 and L2. d= | L1-L2 |
2. Move the pointer from the head by the difference of "d" with respect to the longer list.
3. Now the length of the list from the moved pointer is the same as the length of the other list.
4. Scan both lists and compare the nodes until the addresses match or the list reaches the end.

With this algorithm, the execution time remains O (n + m) and the memory efficiency can be O (1).

Example

Implementation

Intersect.java

class Intersect{
  public LinkedListNode findIntersect(LinkedListNode head1,LinkedListNode head2) {

    LinkedListNode list1node = null;
    int list1length = getLength(head1);
    LinkedListNode list2node = null;
    int list2length = getLength(head2);

    int length_difference = 0;
    if(list1length >= list2length) {
      length_difference = list1length - list2length;
      list1node = head1;
      list2node = head2;
    } else {
      length_difference = list2length - list1length;
      list1node = head2;
      list2node = head1;
    }

    while(length_difference > 0) {
      list1node = list1node.next;
      length_difference--;
    }

    while(list1node != null) {
      if(list1node == list2node) {
        return list1node;
      }

      list1node = list1node.next;
      list2node = list2node.next;
    }
    return null;
  }

  private int getLength(
    LinkedListNode head) {      
    int list_length = 0;
    while(head != null) {
      head = head.next;
      list_length++;
    }
    return list_length;
  }
}