160. Intersection of Two Linked Lists (Hash Table, Linked List, Two Pointers)

링크 - https://leetcode.com/problems/intersection-of-two-linked-lists/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

우리는 각 노드들을 계속 앞으로 이동시키고 null이 나오면 서로의 head로 이동하여 움직임으로써 교차 노드 혹은 교차가 없을시 None에 도달할 수 있다.

1. 교차 노드가 있을 경우, 아래 그림과 같이 node1은 a+c+b를 움직일 것이고, node2는 b + c+ a를 움직일 것이므로 결국 교차 node에 도달할 때 까지 두 노드는 같은 거리를 탐색하게 된다.

2. 교차 노드가 없을 경우, node1은 a + b를 움직일 것이고, node2는 b + a를 움직이고 서로 None을 가리키게 될 것이다. 

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        node1 = headA
        node2 = headB

        while node1 != node2:
            node1 = node1.next if node1 is not None else headB
            node2 = node2.next if node2 is not None else headA

        return node1

Complexity

Time Complexity: O(N + M)

Space Complexity: O(1)