Intersection Of Two Linked Lists

Yohan Kim·2021년 9월 12일
0

problem

두개의 링크드 리스트의 겹치는 노드를 반환하는 문제입니다.
https://leetcode.com/problems/intersection-of-two-linked-lists

solution

//problem : 160
/**
 * 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) {
        set<ListNode* > set;
        pair<std::set<ListNode*>::iterator,bool> it;

        while(headA){
            it = set.insert(headA);
            headA = headA->next;
        }
        while(headB){
            it = set.insert(headB);
            if(it.second == false){
                return *it.first;
            }
            headB = headB->next;
        }
        return NULL;
    }
};

후기

자료구조 set을 이용해서 만들어 보았습니다.
추가적인 메모리가 nodeA,B를 합친 것 보다 더 많이 필요하고, 성능도 그리 좋지 못했습니다.

정답을 맞추고 나서 다른 분들의 코드를 찾아보았는데,
이 문제에서의 핵심은 길이가 다른 linked-list를 길이를 맞추고 그 후 부터 검사하는 것 이었습니다.

문제를 푸는 것보다 이 문제를 어떻게 하면 더 잘 해결할 수 있을까를 고민해봐야하는데 생각하기 쉬운길로 간 것 같아 아쉽습니다.

profile
안녕하세요 반가워요!

0개의 댓글