Python에서 두 연결 목록의 교차점

두 개의 연결 목록 A와 B가 있다고 가정하고 이러한 연결 목록에는 요소가 거의 없습니다. 교차점의 참조를 반환해야 합니다. 입력은 IntersectionVal =8, A =[4,1,8,4,5], B =[5,0,1,8,4,5], skipA =2 및 skipB =3이며, 이들은 건너뛰는 데 사용됩니다. A의 2개 요소와 B의 3개 요소를 건너뜁니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• d라는 지도 정의
• headA가 null이 아닌 동안
  • d[headA] :=1
  • headA :=headA의 다음
• headB가 null이 아닌 동안
  • d
    의 headB인 경우
    • 리턴 헤드B
  • 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'