•
문제 설명 : 두 연결리스트의 순회 중, 공통된 첫 노드를 반환
•
풀이 방법
◦
prev 을 사용하는 양방향 연결리스트가 아니며, 값만 다르고 메모리 영역이 다른 객체일수도 있다.
◦
그래서 하나의 연결리스트의 정보를 Hash Table에 저장하여 다른 연결리스트 순회 시 사용하였다.
•
시간복잡도 :
•
성공 코드
# 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]:
headA_info = set()
while headA != None:
headA_info.add(headA)
headA = headA.next
while headB != None:
if headB in headA_info:
return headB
headB = headB.next
return None
Python
복사