링크드 리스트의 겹침 유무 확인법 (파이썬, 변수참조, 메모리참조)

                                    ⭐🌟 Follow up!
time complexity : O(n + m)
space complexity : O(1)

                                    # Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """

        # space: O(n)
        a_set = set()
        while headA != None:
            a_set.add(headA)
            headA = headA.next

        while headB != None:
            if headB in a_set:
                return headB
            headB = headB.next

        return None

                                    intersectVal = 1

[1,2,3]
[3,2,1]
skipA = 0
skipB = 2

    1 2 3
3 2 1

                                    error message
The two lists should be the same starting from the intersection point.

                                    1. val값은 intersect 여부와 상관없다.
- skipA, skipB 값이 intersect 위치를 결정한다.

2. 반드시 같은 길이에서 시작해야한다.
121
  123
차람 intersect위치로 부터 남은 list의 갯수가 서로 달라선 안된다.

👉 핵심은 같은 메모리 참조를 가지는 intersect의 시작점을 찾는 것이다.

🤔 결국 같은 길이에서 시작 할 수 밖에 없으니, 큰 길이를 미리 줄여도 되는 거 아닌가?

                                    ✅ 큰길이를 가진 LinkedList를 작은 길이에 맞춘다.

✅ 하나씩 탐색하면서, 같은 메모리를 참조하는지 확인한다.
>>> 메모리 참조 ?

                                    # Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """

        # space: O(1)
        a_len = 0
        b_len = 0

        a_tmp = headA
        b_tmp = headB

        while a_tmp != None:
            a_len += 1
            a_tmp = a_tmp.next

        while b_tmp != None:
            b_len += 1
            b_tmp = b_tmp.next

        max_len = max(a_len, b_len)
        dt = abs(a_len - b_len)

        if max_len == a_len:
            for i in range(dt):
                headA = headA.next
        else:
            for i in range(dt):
                headB = headB.next

        has_intersection = False
        while 1:
            if headA == None and headB == None:
                break

            if headA == headB:
                has_intersection = True
                return headA

            headA = headA.next
            headB = headB.next

        if not has_intersection:
            return None

                                    🗝️ 서로 다른 두 포인터가 하나는 nodeA에서 nodeB로, 하나는 nodeB에서 nodeA로 같은 속도로
순환한다면 intersection을 발견할 수 있다.

✅      ➕ = intersection 지점
[a1, a2, c1➕, c2, c3]
[b1, b2, b3, c1➕, c2, c3]

pointer 1 이동 경로
[a1, a2, c1➕, c2, c3, none, b1, b2, b3, c1➕, c2, c3, none]
pointer 2 이동 경로
[b1, b2, b3, c1➕, c2, c3, none, a1, a2, c1➕, c2, c3, none]

                                                                                  v
[a1, a2, c1➕, c2,   c3, none, b1,  b2, b3, c1➕, c2, c3, none]
                                              v
[b1, b2, b3,    c1➕, c2, c3, none, a1, a2, c1➕, c2, c3, none]

🏃‍♂️‍➡️ 같은 속도로 포인터가 이동되기 때문에 결국 뒤의 c1➕ 에서 만난다
❌ 겹침이 존재하지 않으면 결국 마지막 None에서 만난다.

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """

        dummy1, dummy2 = headA, headB
        while dummy1!= dummy2:
            dummy1 = dummy1.next if dummy1 else headB
            dummy2 = dummy2.next if dummy2 else headA
        return dummy1