Intersection of Two Linked Lists

두 연결 리스트에서 같은 주소를 가지는 노드를 구하는 문제

처음에는 동일한 숫자를 가지기 시작하는 노드를 구하는 문제인줄 알았다.

한발 더 나아가서 O(m + n) 시간과 O(1) 메모리 사용을 하여 풀어보라고 한다.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int CountList(ListNode *head)
    {
        int counter{0};
        ListNode *temp{head};
        
        while (temp != nullptr)
        {
            counter++;
            
            temp = temp->next;
        }
        
        return counter;
    }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        
        int counterA{0};
        int counterB{0};
        
        counterA = CountList(headA);
        counterB = CountList(headB);
        
        ListNode *tempA{headA};
        ListNode *tempB{headB};

        if (counterA > counterB)
        {
            tempA = headB;
            tempB = headA;
        }

        for (int i = 0; i < abs(counterA - counterB); i++)
        {
            tempB = tempB->next;
        }
        
        while (tempA != tempB)
        {
            tempA = tempA->next;
            tempB = tempB->next;
        }
        
        return tempA;
    }
};