leetcode easy : Intersection of Two Linked List

https://leetcode.com/problems/intersection-of-two-linked-lists/description/

Intersection of Two Linked Lists - LeetCode

 

오 EASY인데 엄청 만만하지는 않고 한 5분정도 고민하게 만드는 문제였다.

푸는 방법은 간단하다.

일단 A랑 B 둘다 끝까지 가본다.

끝까지 가서 같은 지점에 도착해있으면 intersection이 있는거다. 끝 노드가 다르면 null을 리턴하면 된다.

그리고 끝까지 가면서 A랑 B의 길이를 세야된다.

그 길이차를 계산하고 A랑 B중에 어느쪽이 더 긴지 봐서 교차점을 찾으면된다.

 

# 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]:
        # 끝까지 가면서 길이 계산
        len1, len2 = 1, 1
        nodeA, nodeB = headA, headB
        while nodeA.next:
            len1 += 1
            nodeA = nodeA.next
        while nodeB.next:
            len2 += 1
            nodeB = nodeB.next

        # 끝 노드가 다르면 intersection이 없는거
        if nodeA != nodeB:
            return None

        # 길이차만큼 긴쪽의 리스트를 node = node.next 하기
        nodeA, nodeB = headA, headB
        diff = abs(len1 - len2)
        if len1 > len2:
            while diff:
                nodeA = nodeA.next
                diff -= 1
        else:
            while diff:
                nodeB = nodeB.next
                diff -= 1
        
        # 그리고 둘이 같아질때까지 한스텝씩 next
        while nodeA != nodeB:
            nodeA = nodeA.next
            nodeB = nodeB.next

        return nodeA