[LeetCode] Intersection of Two Linked Lists (switch)

솔루션

# 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) -> ListNode:
        p1 = headA
        p2 = headB
        
        while p1 != p2:
            if p1:
                p1 = p1.next
            else:
                p1 = headB

            if p2:
                p2 = p2.next
            else:
                p2 = headA
        
        return p1

 

while 문 조건을 p1 != p2

기준으로 두 node가 같은 경우 while문 중단한다.

node가 다른 경우 계속 next로 이동하는데 만약 끝까지 도달했음에도 p1 == p2가 아닌 경우

즉, p1의 next가 None인 경우 p1은 headB를 받아서 다시 next를 수행한다.(p2의 경우는 반대로)

 

무식한 것 같지만 나름 효율적인 방법이기도 하다.

그러다 보면 결국 겹치는 부분이 발생하는데 그 때 return을 하게 되는 것이다.

 

서로 다른 노드를 강제로 서로 다른 노드로 스위치하면서 계속이어지게 만들어서 조건을 찾는 것이다.

---

디버깅 코드와 같이 보자.

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p1 = headA
        p2 = headB
        
        while p1 != p2:
            if p1:
                print("P1", p1.val)
                p1 = p1.next
            else:
                # print(p1.val)
                p1 = headB
                # print(p1.val)
            if p2:
                print("P2",p2.val)
                p2 = p2.next
            else:
                p2 = headA
        
        return p1

A_dummy = A = ListNode(None)
B_dummy = B = ListNode(None)
HA = [4,1,8,4,5]
HB = [5,6,1,8,4,5]

while HA:
    A.next = ListNode(HA[0])
    A = A.next
    HA.pop(0)

while HB:
    B.next = ListNode(HB[0])
    B = B.next
    HB.pop(0)

# while A_dummy:
#     print(A_dummy.val)
#     A_dummy = A_dummy.next

Solution().getIntersectionNode(A_dummy, B_dummy)

예제 1번의 경우다.

 

 

print로 p1과 p2가 어떻게 움직이는 지 찍어봤다.

 

8 이라는 node에서 처음 같은 위치에 있는 것을 알 수 있다.

 

다른 솔루션

class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        curA, curB = headA, headB
        begin, tailA, tailB = None, None, None

        # a->c->b->c
        # b->c->a->c
        while curA and curB:
            if curA == curB:
                begin = curA
                break

            if curA.next:
                curA = curA.next
            elif tailA is None:
                tailA = curA
                curA = headB
            else:
                break

            if curB.next:
                curB = curB.next
            elif tailB is None:
                tailB = curB
                curB = headA
            else:
                break

        return begin

이 솔루션도 본질적으로는 위와 같다.

다만 다른점은 begin, tailB, tailB를 사용해서 푼다는 점 말고는.

 

출처: github.com/jiapengwen/LeetCode/blob/master/Python/intersection-of-two-linked-lists.py