Intersection Point of Two Lists

설명

두 개의 링크 된 목록의 머리가 전달되므로 두 개의 링크 된 목록이 실제로 교차하는지 확인하고,
그 교차로를 반환하는 알고리즘을 구현해 봅시다. 교차점이 없으면 null을 반환합니다.
교차점이라고 하는 것은 Node의 메모리에 있는 주소가 동일하다는 것을 의미합니다.

다음 예제에서는 두 목록 모두 교차하지 않습니다.

다음 예제에서는 교차점인 12개의 데이터를 보유하는 노드가 있으므로 해당 노드를 반환합니다.

Solution1

우선, 최초로 생각하는 구현의 방법은 첫 번째의 Linked List의 노드가 두 번째의 Linked List에도 존재하는가
실행 시간이 O(m * n)의 효율이 나쁜 알고리즘입니다 (m와 n은 Linked List의 길이).
이 경우 런타임은 느리지만 Space Complexity는 두 개의 포인터를 사용하여 스캔하기 때문에 O (1)입니다.

Solution2

다만, 메모리에 여유가 있어 실행 시간을 보다 효율적으로 향상시키고 싶다고 합시다. 이 경우 먼저 머리에 떠오르는 것은
HashTable을 사용한 데이터 구조를 사용하는 것입니다. 그래서 Java의 HashSet을 사용하여 구현합니다.
우선 하나의 Linked List의 요소를 선형 주사하면서 HashSet에 Node를 추가해 갑니다.
그런 다음 두 번째 링크 된 목록에 대해 선형 스캔하면서 HashSet에 동일한 노드가 있는지 확인합니다.
HashSet의 요소에의 액세스는 물론 O(1)이므로, 이 구현의 실행 시간은 O(m + n)가 되어, 효율 좋게 되었습니다.

구현

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

이제 링크된 목록에 엄청난 양의 데이터가 있다고 가정하여 좀 더 메모리 효율성을 향상시킬 수 없는지 생각해 봅시다.
먼저 두 링크된 목록이 같은 크기라고 가정해 봅시다.
이 경우 두 맨 위에서 서로 다른 두 포인터를 사용하여 노드의 주소를 비교할 수 있습니다.
이 주소가 일치하면 교차로임을 의미합니다.
일치하지 않으면 두 포인터를 동시에 하나씩 이동하여 주소를 비교합니다.
교차점이 발견되거나 두 목록이 모두 없어질 때까지 이 과정을 반복합니다.
이제 목록의 길이가 다른 경우 문제를이 개념을 사용해 보겠습니다.

두 링크 된 목록의 길이를 검색 : L1과 L2로 설정합니다.

L1과 L2의 길이 차이를 계산합니다. d = | L1-L2 |

긴 리스트에 대해서 「d」의 차분만, head로부터 포인터를 이동시킵니다.

여기서, 이동시킨 포인터로부터의 리스트의 길이와 다른 리스트의 길이가 같게 됩니다.

두 목록을 모두 스캔하고 주소가 일치하거나 목록이 마지막에 도달 할 때까지 노드를 비교합니다.

이 알고리즘이라면, 실행 시간은 O(n + m) 그대로, 메모리의 효율을 O(1)로 할 수 있습니다.

예

구현

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