33. Intersection of Two Linked Lists

문제

두 연결 리스트가 교차하는 곳의 노드를 반환하시오.

교차하는 곳이 없으면 null을 반환하시오.

두 연결 리스트에 사이클은 없다고 가정함.

 

해결 방식

https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1215/discuss/403600/Python-clean-solution

https://aaronice.gitbook.io/lintcode/linked_list/intersection-of-two-linked-lists

연결리스트 A를 가리키는 pA 포인터, 

연결리스트 B를 가리키는 pB 포인터 설정.

 

pA와 pB가 같지 않다면 둘 다 한 칸씩 앞으로 이동.

만약 pA가 연결 리스트 끝에 다다르면 pB로 이동해서 한 칸씩 이동.

pB가 연결 리스트 끝에 다다르면 pA로 이동해서 한 칸씩 이동.

 

pA와 pB가 같으면 해당 노드 반환.

def getIntersectionNode(headA, headB):
    a_pointer, b_pointer = headA, headB
    while a_pointer != b_pointer:
        a_pointer = a_pointer.next if a_pointer else headB
        b_pointer = b_pointer.next if b_pointer else headA
    return a_pointer