160. Intersection of Two Linked Lists

연결 리스트의 교차점을 찾는 문제다.
교차점을 하나 찾으면 그 뒤의 노드들도 모두 같음이 보장된다.

Solution

skipA, skipB 같은 수들을 줘서 문제 이해가 더 어려웠다.
얘를 사용해야 한다는거야 뭐야 왜 주는거야

두 리스트의 순서를 반대로 이어 붙인 두 리스트를 비교하면 길이를 신경쓰지 않고 단순 반복문으로 교차점을 찾을 수 있다.

listA = [4,1,8,4,5], listB = [5,6,1,8,4,5] 가 있는 경우:
4, 1, 8, 4, 5 - 5, 6, 1, 8, 4, 5
5, 6, 1, 8, 4, 5, - 4, 1, 8, 4, 5

# 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]:
        a = headA
        b = headB

        while (a and b):
            if a == b: return a # 교차점 발견
            a = a.next
            b = b.next

            if not a and not b: return None # 둘 다 끝나면 null 반환
            if not a: a = headB # linkedlistA-linkedlistB 연결
            if not b: b = headA # linkedlistB-linkedlistA 연결
        
        return None

시간 복잡도

결국 두 개의 연결 리스트의 길이만큼 순환하면서 검사를 수행하기 때문에 시간 복잡도는 O(n+m)이다.