LeetCode 160(Intersection of Two Linked Lists, Python)

1. 문제 링크

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

2. 문제 설명

• 사이클이 없는 두 개의 연결 리스트(Linked List)가 주어졌을 때 교차하는 곳을 시작점으로 하는 연결 리스트를 반환하는 문제
• 예시) a1 → a2 → c1 → c2 → c3와 b1 → b2 → b3 → c1 → c2 → c3가 주어지면 c1에서 교차하기 때문에 연결 리스트 c1 → c2 → c3를 반환

3. 처음 풀이 

• a1을 시작으로 .next를 통해 한 칸 씩 앞으로 가며 끝까지 집합 seen에 저장하고
• b1부터 시작하여 seen 에 있는 지 판단하여 아니면 한 칸 전진, 이미 나온 노드면 교차점으로 판단 하여 반환
  
• 시간 복잡도 O(m+n)

# 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]:
        seen = set() #집합 seen 생성
        while headA: #headA의 끝이 나올 때까지
            seen.add(headA) #headA의 현재 노드를 seen에 저장
            headA = headA.next #다음 노드로 이동
        while headB: #headB의 끝이 나올 때까지
            if headB in seen: #현재 노드가 seen에 있으면 교차점이므로 반환
                return headB
            headB = headB.next #그렇지 않으면 다음 노드로 이동
        return #headB 끝까지 갔다면 교차점이 없으므로 None을 반환

• 120ms (80.30%), 32.3mb(5.70%)

4. 다른 풀이 

• 시간 복잡도 O(m+n)
• 처음 풀이에 비해 메모리 효율적
• 아이디어는 주어진 두 연결 리스트를 두 방향으로 이어 붙여 비교 
• 즉, headA: a1a2c1c2c3와 headB: b1b2b3c1c2c3가 주어졌을 때
• headA-headB 순으로 연결하면 a1a2c1c2c3→b1b2b3c1c2c3
• headB-headA 순으로 연결하면 b1b2b3c1c2c3 → a1a2c1c2c3
• 이고 같은 순서에 있는 node에 비교하면 9번째인 c1에서 node가 같고 여기부터가 교차점

# 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]:
        currentA = headA
        currentB = headB
        while currentA != currentB:
            if currentA:
                currentA = currentA.next #headA를 한 칸 씩 전진
            else:
                currentA = headB #headA가 끝이 났으면 그 뒤에 headB를 이어 붙이고 한 칸 씩 전진
            if currentB:
                currentB = currentB.next #headB를 한 칸 씩 전진
            else:
                currentB = headA #headB가 끝이 났으면 그 뒤에 headA를 이어 붙이고 한 칸 씩 전진
        return currentA #headA, headB의 node가 같아진 순간 반환, 교차점이 없다면 끝까지 가서 None 반환