Gidhub BE Developer

LeetCode : 160. Intersection of Two Linked Lists

2020-12-11
goodGid

160. Intersection of Two Linked Lists

Problem

Write a program to find the node at which the intersection of two singly linked lists begins.
You may assume there are no cycles anywhere in the entire linked structure.

Example

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Code (20. 12. 11)

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode aTempNode = headA;
        ListNode bTempNode = headB;

        while (headA != headB) {
            if (headA == null) {
                headA = bTempNode; // [1]
            } else {
                headA = headB.next;
            }

            if (headB == null) {
                headB = aTempNode; // [2]
            } else {
                headB = headB.next;
            }
        }
        return headA;
    }
}
  • 아이디어가 너무 참신하고 신선했다.

    풀지 못해서 답을 찾아보고 풀었다.

    ‘어떻게 저런 아이디어를 생각해냈지?’ 라는 생각이 들었다.

  • 이 아이디어의 핵심은

    [1], [2] 코드를 이해하는 것이다.

A List.size = 3
B List.size = 5

headA는 A List를 다 탐색하고 B List를 탐색한다.
    --> 3 + 5 = 8번
headB는 B List를 다 탐색하고 A List를 탐색한다.
    --> 5 + 3 = 8번

즉 A+B List를 돌면서 교집합을 찾는다.
= 동일한 List에 대해 순회를 한다.
= 교집합이 있다면 가리키는 Node가 동일해지는 시점이 온다.
= 교집합이 없다면 headA와 headB는 두개다 종단엔 null이 된다.

ex) listA = [4,1,8,4,5] / listB = [5,6,1,8,4,5]
[1], [2] 라인까지 가면
headA와 headB의 시작되는 위치에서
교집합이 되는 Node까지의 거리는 동일하다.

headA는 4를 가리키고 headB는 6을 가리킨다.
그리고 각각 교집합이 되는 8 Node까지의 거리는 2개이다.
  • 위 아이디어가 가능한 이유는

    You may assume there are no cycles anywhere in the entire linked structure. 라는 조건이 있기 때문이다.

  • 조금 더 설명을 더하자면

A 집합 = [1,2]
B 집합 = [3,4]
C 집합 = [5,6] (= 교집합)

A List : [1,2,5,6] = A 집합 + C 집합
    --> A 탐색 -> C 탐색 -> B 탐색
B List : [3,4,5,6] = B 집합 + C 집합
    --> B 탐색 -> C 탐색 -> A 탐색

결과적으로 같은 Node에 대해 탐색한다고 볼 수 있다.
  • 최대한 이해할 수 있도록 설명을 작성해봤는데

    잘 이해가 되었으면 좋겠다 !


Reference


Comments

Index