파이썬(Python)으로 두 연결 리스트의 교차점 찾기

문제 개요

두 개의 연결 리스트 A와 B가 있다고 가정해 보겠습니다. 각 리스트에는 여러 개의 노드가 있으며, 우리가 구해야 할 것은 두 리스트가 만나는 교차점(intersection node)에 대한 참조입니다.

예를 들어 입력이 intersectionVal = 8, A = [4,1,8,4,5], B = [5,0,1,8,4,5], skipA = 2, skipB = 3이라면, 이 값들은 A에서 앞의 2개 노드를, B에서 앞의 3개 노드를 건너뛴 지점부터 두 리스트가 같은 노드('8')를 공유한다는 의미입니다.

해결 알고리즘

이 문제는 해시맵(딕셔너리)을 활용하면 간단하게 해결할 수 있습니다. 먼저 첫 번째 리스트의 모든 노드를 기록한 뒤, 두 번째 리스트를 순회하며 처음으로 일치하는 노드를 찾으면 됩니다. 단계는 다음과 같습니다.

• d라는 이름의 맵(딕셔너리)을 정의합니다.
• headA가 null이 아닌 동안 반복합니다.
  • d[headA] := 1 로 방문 표시를 합니다.
  • headA := headA의 다음 노드로 이동합니다.
• headB가 null이 아닌 동안 반복합니다.
  • 만약 headB가 d에 존재한다면,
    • headB를 반환합니다. (교차점 발견)
  • headB := headB의 다음 노드로 이동합니다.
• 반복이 끝날 때까지 교차점을 찾지 못하면 null을 반환합니다.

예제 구현

더 나은 이해를 돕기 위해 다음 파이썬 구현을 살펴보겠습니다.

class ListNode:
   def __init__(self, data, next = None):
      self.data = data
      self.next = next
class Solution(object):
   def getIntersectionNode(self, headA, headB):
      """
      :type head1, head1: ListNode
      :rtype: ListNode
      """
      dict = {}
      while headA:
         dict[headA]=1
         headA = headA.next
      while headB:
         if headB in dict:
            return headB
         headB = headB.next
      return None
headA = ListNode(4)
headB = ListNode(5)
Intersect = ListNode(8, ListNode(4, ListNode(5)))
headA.next = ListNode(1, Intersect)
headB.next = ListNode(0, ListNode(1, Intersect))
ob1 = Solution()
op = ob1.getIntersectionNode(headA, headB)
print("Intersection:",op.data)

입력

headA = ListNode(4)
headB = ListNode(5)
Intersect = ListNode(8, ListNode(4, ListNode(5)))
headA.next = ListNode(1, Intersect)
headB.next = ListNode(0, ListNode(1, Intersect))

출력

Intersected at '8'

복잡도 분석

시간 복잡도: O(n + m) — 첫 번째 리스트를 한 번 순회하고(n), 두 번째 리스트도 최대 한 번 순회하기 때문입니다(m).

공간 복잡도: O(n) — 첫 번째 리스트의 모든 노드를 딕셔너리에 저장해야 하므로 추가 메모리가 필요합니다.

참고로 추가 메모리 없이 O(1) 공간으로 해결하려면, 두 포인터가 각각의 리스트 끝에 도달하면 서로 다른 리스트의 시작점으로 전환하는 투 포인터(two-pointer) 기법을 사용할 수 있습니다. 두 포인터는 교차점에서 만나거나, 교차점이 없다면 동시에 null에 도달하게 됩니다.