(C++) - LeetCode (easy) 160. Intersection of Two Linked Lists

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

Intersection of Two Linked Lists - LeetCode

linked list를 이용한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. headA, headB의 길이를 aLength, bLength선언 후 각각 저장해줍니다.

2. 두 list의 최소길이를 minLength에 저장해줍니다.

📔 풀이과정

두 list의 시작지점을 일치시킨다고 생각해봅니다.

1. headA의 시작점은 aLength - minLength이며 headB의 시작점은 bLength - minLength로 둡니다.

이로써 list 길이가 서로 달라도 시작점을 끝점으로부터 같은 길이만큼 조절해 일치시킴으로써 교차점을 찾을 수 있습니다.

2. aCur, bCur를 선언해 해당 길이만큼 시작점을 이동시킨뒤 while문을 수행해 둘이 같다면 바로 현재 node를 반환합니다.

3. while문이 끝났다면 교차점이 없으므로 NULL을 반환합니다.

---

📕 Code

📔 C++

/**
 * 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) {
        int aLength = 0;
        int bLength = 0;
        
        ListNode *aCur = headA;
        ListNode *bCur = headB;

        for(ListNode *cnt = headA; cnt != NULL; cnt = cnt -> next) aLength++;
        for(ListNode *cnt = headB; cnt != NULL; cnt = cnt -> next) bLength++;

        int minLength = min(aLength, bLength);

        for(int i = 0; i < aLength - minLength; i++) aCur = aCur->next;
        for(int i = 0; i < bLength - minLength; i++) bCur = bCur->next;

        while(aCur != NULL && bCur != NULL) {
            if(aCur == bCur) return aCur;
            aCur = aCur -> next;
            bCur = bCur -> next;
        }

        return NULL;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.