[Top Interview Questions] 160. Intersection of Two Linked Lists

정답)

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

        while headA != headB:
            if headA:
                headA = headA.next
            else:
                headA = rootB
            
            if headB:
                headB = headB.next
            else:
                headB = rootA
        
        return headA

문제)

문제출처

 

2개의 링크드 리스트들이 존재합니다. 2개의 링크드 리스트들의 head 노드들 headA, headB가 주어졌을 때 이 두 리스트들이 만나는 지점의 노드를 리턴하시오. 만약 2개의 리스트들에 교차점이 존재하지 않는다면 null을 리턴하시오. 

 

이 리스트들은 원래의 구조를 유지한 채 정답이 리턴되어야 합니다. 

 

예시 1)

 

listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]

output = 8

 

예시 2)

 

listA = [1,9,1,2,4], listB = [3,2,4]

output = 2

 

예시 3)

 

listA = [2,6,4], listB = [1,5]

output = null

 

제한)

1 <= listA의 개수(m), listB의 개수(n) <= 30000

1 <= Node.val <= 100000

 

도전)

O(m+n)의 시간복잡도와 O(1)의 공간복잡도를 가진 정답을 제출하시오.

풀이)

기본원리)

listA와 listB 두 개를 동시에 선형 시켜줍니다.

 

선형 하는 도중에 리스트의 끝에 도달하게 되면 반대편 리스트를 선형 하게 해 줍니다. 

그런 식으로 선형 하다 보면 사이클이 있든 없든 같은 노드에 도달하는 순간이 존재합니다.

 

사이클이 있는 2개의 리스트들을&nbsp; 선형 하는 &nbsp;방식

 

사이클이 없는&nbsp; 2개의 리스트들을&nbsp; 선형 하는 &nbsp;방식

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    리스트를 선형하기 전 head node들을 변수에 저장
    
    headA와 headB가 같지 않을동안:
        Null에 다다를때까지 선형
        다다른다면 반대 list에서 다시 선형
    
    headA와 headB가 같다면 둘 중 하나를 리턴

초기 세팅)

리스트들을 선형 하기 전 각 리스트의 head 노드의 위치를 알아야 할 필요가 있습니다.

 

그림에서도 봤듯이 한 리스트의 선형이 끝나면 그 즉시 반대쪽 head 노드로 가서 다시 리스트를 진행합니다. 

그렇기 때문에 각 리스트의 시작점을 알아야 할 필요가 있습니다.

 

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        rootA = headA
        rootB = headB

선형 그리고 위치 변경)

앞서 말했듯이 각 리스트들을 먼저 선형 시켜줍니다. 만약 현재 가리키고 있는 노드 (즉, headA 혹은 headB)가 Null이 아닌 경우에는 .next() 메서드를 사용해 리스트를 선형 해줍시다. 

 

a와 b 모두 Null이 아닌 실제 노드를 가리키고 있기에&nbsp; 한 칸 &nbsp;선형

만약 선형과정 중 현재 가리키고 있는 노드가 Null일 경우, 그 리스트의 선형이 끝난 거겠죠.

만약 headA가 Null이라면 headA가 listB를 선형 할 수 있도록 해줍니다.

만약 headB가 Null이라면 headB가 listA를 선형 할 수 있도록 해줍니다.

 

b가 null에 도달했기 때문에 listA로 넘어가 선형

그렇게 두 노드 모두 서로 다른 리스트를 선형 하기 시작했다면 그 노드들은 현재 동등한 위치에 있을 겁니다.

 

a와 b가 동등한 위치에 위치함

이 상태에서 계속 선행하다 보면

사이클이 없는 이 리스트들처럼 null에 도달하거나

사이클이 있다면 사이클의 시작점 노드에 도달합니다.

 

그렇게 되면 이 while 루프는 종료됩니다.

 

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        rootA = headA
        rootB = headB

        while headA != headB:
            if headA:
                headA = headA.next
            else:
                headA = rootB
            
            if headB:
                headB = headB.next
            else:
                headB = rootA

headA == headB)

while문이 끝나 headA와 headB 노드들이 같다면 headA 혹은 headB를 리턴하면 됩니다.

 

사이클이 없다면 null

사이클이 있다면 사이클의 시작점 노드가 리턴됩니다.

 

 

이번 문제는 그림에서 이미 디버깅 과정이 충분히 설명된 거 같아 따로 디버깅 섹션을 놓지는 않았습니다. 2개의 링크드 리스트들을 어떻게 선형 할지 이해하는 게 중요했던 문제였습니다. 

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)