160. Intersection of Two Linked Lists

두개의 링크드 리스트가 있을 때, 두개의 링크드 리스트가 한 지점부터 인터섹션 되는 경우가 있다. 그 때 해당 인터섹션되는 지점부터의 링크드 리스트를 리턴하라.

 

---

solution 1.

두개의 링크드 리스트를 리스트에 넣고 리버스하여 같지 않은 것이 있을 때 이전값이 해당 노드의 값이라고 생각했다.

하지만, 노드의 값으로는 판단할 수 없었고 노드의 값이 같아도 인터섹션이 되지 않는 경우도 있다.

 

solution 2.

각 링크드 리스트를 처음부터 끝까지 가되, 처음 링크드 리스트를 처음부터 끝까지 갈 때 값이 아닌 링크드 리드스트 자체를 셋에 넣는다. 그 후, 다음 링크드 리스트를 순회할 때 해당 링크드 리스트가 링크드 리스트에 존재하는지 파악한다. 있으면 그 자리에서 리턴한다.

 

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        inter_set = set()
        curr = headA
        while curr:
            inter_set.add(curr)
            curr = curr.next
        curr = headB
        while curr:
            if curr in inter_set:
                return curr
            curr = curr.next
        return None