leetcode 141:Linked List Cycle問題と解答
問題の再現:は、チェーンテーブルを与える、ループが存在するか否かを判定する(できるだけ余分な空間を使用しない) .
分析の考え方:
1、暴力解法、すなわち、2番目のノードから、それぞれの新しいノードを前のすべてのノードと比較し、サイクルがあるか否かを判断し、時間複雑度をO(N^2)、空間複雑度をO(N)とする
2、スピードポインタの思想を採用して、つまり2つのポインタでそれぞれチェーンテーブル全体を遍歴して、スピードポインタは毎回1つのノードを前進して、スピードポインタは毎回2つのノードを前進して、もし2つのポインタが出会ったら、それでは循環があると判断します;ループは存在しません.時間的複雑度はO(N),空間的複雑度はO(1)である.
問題解決:
分析の考え方:
1、暴力解法、すなわち、2番目のノードから、それぞれの新しいノードを前のすべてのノードと比較し、サイクルがあるか否かを判断し、時間複雑度をO(N^2)、空間複雑度をO(N)とする
2、スピードポインタの思想を採用して、つまり2つのポインタでそれぞれチェーンテーブル全体を遍歴して、スピードポインタは毎回1つのノードを前進して、スピードポインタは毎回2つのノードを前進して、もし2つのポインタが出会ったら、それでは循環があると判断します;ループは存在しません.時間的複雑度はO(N),空間的複雑度はO(1)である.
問題解決:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode *fast = head, *slow = head;
while(fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
if(fast == slow) //if they equal, it has a cycle
return true;
}
return false; //while a pointer is NULL, it doesn't have a cycle
}