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. Screen Shot 2020-01-08 at 22.18.43.png In the following example, there is a node that holds 12 data at the intersection, so that node is returned. Screen Shot 2020-01-08 at 22.19.25.png

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

Screen Shot 2020-01-08 at 22.50.38.png Screen Shot 2020-01-08 at 22.51.11.png Screen Shot 2020-01-08 at 22.51.47.png Screen Shot 2020-01-08 at 22.52.08.png Screen Shot 2020-01-08 at 22.52.28.png

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;
  }
}

Recommended Posts

Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm exercise 6
Algorithm Gymnastics 24 Reverse a Linked List
Python algorithm
Algorithm exercises 13
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List
Python memorandum (algorithm)
Dictionary learning algorithm
String search algorithm