링크드 리스트가 주어졌을 때, 순환하는 구조인지 판별하는 문제입니다.
https://leetcode.com/problems/linked-list-cycle
class Solution {
public:
bool hasCycle(ListNode *head) {
map<ListNode*,int> m;
while(head != NULL){
if(m.find(head) == m.end()){
m[head] = head->val;
}else{
return true;
}
head = head->next;
}
return false;
}
};
처음에 짠 코드입니다. map 자료구조를 이용해서 넣고 한칸씩 전진하면서 찾아서 발견하면 순환하는 것이므로 true를 리턴합니다.
코드의 문제점은 가장 안좋은 경우에는 원이 마지막 노트에서 마지막으로 두번째에 순환구조가 연결되어 있다면,
map에 n-1개의 노드가 들어가고, find()의 iter이 돌아가는 횟수가
1,2,3,4,5,6,7,8.....n-2까지 가므로 O(n^2)이 될것입니다.
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* fast = head;
while(fast && fast->next ){
head = head->next;
fast = fast->next->next;
if(head == fast) return true;
}
return false;
}
};
와... 어떻게 이런 생각을 할 수 있을까, 추가적인 메모리 소모도 없고
코드도 간결하다. 빠르게 다가가는 iter가 순환형 구조에서는 언젠가 따라잡으니까 (간격이 한칸 씩 줄어든다.) 대단하다는 생각이 들었다.