LeetCode 160. Intersection of Two Linked Lists

Acceptance Rate가 높은 문제들 위주로 풀이를 진행중이다.

 

https://leetcode.com/problems/intersection-of-two-linked-lists/

Intersection of Two Linked Lists - LeetCode

 

2개의 Linked Lists의 intersection이 어디서 발생하는지 찾는 문제이다.

 

2중 for문을 사용하면 쉽게 풀 수 있으나(시간복잡도 : O(m*n)), Follow up에 O(m+n)의 시간 복잡도와 O(1)의 공간 복잡도로 풀수 있을지에 대한 질문이 있어서 고민해보았다.

 

두개의 stack에 저장하고 하나씩 추출하는 방법으로 찾는다면, 연결이 끊기는 위치를 찾아 쉽게 풀 수 있겠으나 공간복잡도가 O(m+n)이 되므로 불합격이다.

 

Hash table(dictionary, set)에 하나의 linked list를 저장하고, in 연산을 통해 찾아도 시간복잡도는 O(m+n)이지만, 공간복잡도가 O(n)이 되므로 불합격이다.

 

O(m+n)이라면 while(listA and listB)의 형태로 풀게 될텐데, 이 경우 둘의 intersection을 어떻게 찾을 수 있을까?

 

혼자서는 적절한 답을 찾지못해 solutions를 확인하였다.

 

정답은 각각의 linked list에 다른 linked list를 붙이는 것이다.

 

두 linked lists의 intersection은 list의 중간에서 발생하지 않는다. 즉, 두개의 linked lists를 붙였을 때(listA+listB, listB+listA) intersection이 이루어지는 부분이 같은 위치(n번째 node)에 존재한다는 의미이다.

 

그러나 두 linked lists의 길이가 같다면 굳이 두개의 linked lists를 붙이지 않아도 같은 위치에 intersection이 존재 할 것이고, 효율성을 위해 일반화를 하여야한다.

 

결과 코드는 다음과 같다.

 

# 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]:

       

        a = headA

        b = headB

        while a != b:

            a = headB if not a else a.next

            b = headA if not b else b.next

        return a

 

알고리즘 문제의 최적 해결방법을 찾는데에는 문제가 가지고 있는 특성을 발견하는것이 가장 중요한 것 같다.

 

질문이나 지적은 댓글로..