[leetcode] 160. Intersection of Two Linked Lists

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

 

주어진 두 개의 Linked Lists 를 따라 순회하는 두 개의 포인터를 이용한다.

각 포인터가 Linked List 의 끝에 도달하면, 순회하지 않은 다른 Linked List 로 돌아와 다시 순회를 시작한다.

두 포인터 모두 한 스텝씩 움직이기 때문에, 위와 같이 순회하면 두 포인터는 같은 길이만큼 순회하게된다.

만약 접점이 존재하면, 두 포인터가 해당 접점을 가리키게 된다.

만약 접점이 존재하지 않으면, 두 포인터 모두 None 을 가리키게 된다.

 

 

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if(not headA or not headB): return None

        pa, pb = headA, headB
        while(pa != pb):
            pa = pa.next if pa else headB
            pb = pb.next if pb else headA
        return pa

 

 

---

 

 

 

< English (feedback by ChatGPT) >

 

 

 

We can use the pointers which iterate the each linked list.

(We can use two pointers to traverse the two linked lists.)

 

When the each pointers meet the end of the linked list, they start to iterate through the opposite linked list which didn't traversal.

(When each pointer reaches the end of its list, it switches to the other list and continues traversing.)

 

Since the two pointers move one step at a time, the pointers move same steps as traversal.

(Since both pointers move one step at a time, they will end up traversing the same total number of steps.)

 

If an Intersection exists, the two pointers point the Intersection node.

(If an intersection exists, the two pointers will meet at the intersection node.)

 

If an Intersection doesn't exist, the two pointers point None.

(If no intersection exists, both pointers will eventually point to None.)