두개의 링크드 리스트의 겹치는 노드를 반환하는 문제입니다.
https://leetcode.com/problems/intersection-of-two-linked-lists
//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를 길이를 맞추고 그 후 부터 검사하는 것 이었습니다.
문제를 푸는 것보다 이 문제를 어떻게 하면 더 잘 해결할 수 있을까를 고민해봐야하는데 생각하기 쉬운길로 간 것 같아 아쉽습니다.