문제

릿코드 discussion에 종종 내 코드랑 설명을 쓰는데, 마음에 들어서 그대로 가져와봄. 가끔 도움이 되었는지 star가 올라가는데 뿌듯하다 ㅎㅎ

  • Let L(A) be the number of nodes to visit until list A begins to intersect.
  • Let L(B) be the number of nodes to visit until list B begins to intersect.
  • Let L(C) be the number of nodes to visit from C1 to the tail of the list.

The sizes of list A and list B are L(A)+L(C) and L(B)+L(C), respectively. So if ptr1 starts to traverse list B and ptr2 starts to traverse list A when reaching the end of the list, the distance each pointer moved equals L(A)+L(B)+L(C) by the time the two lists intersect.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *ptr1 = headA;
        ListNode *ptr2 = headB;
        
        if(ptr1 == NULL || ptr2 == NULL) return NULL;
        
        while(ptr1 != ptr2) {
            ptr1 = (ptr1 != NULL) ? ptr1->next : headB;
            ptr2 = (ptr2 != NULL) ? ptr2->next : headA;
        }
        return ptr1;
    }
};