leetcode141-环形链表 leetcode141-环形链表

题目：见leetcode141 解答：官方解答解法一：双指针

bool hasCycle(ListNode *head) { if(head == nullptr || head->next == nullptr) { return false; }//一个元素不算环 ListNode *slow = head; ListNode *fast = head->next; // while(slow != fast) { if(fast == nullptr || fast->next == nullptr) { return false; } slow = slow->next; fast = fast->next->next; } return true; }

时间复杂度：n，空间复杂度：1//快慢两个指针
注：时间复杂度分析：以慢指针为角度，进入环之前，经过N个结点；进入环之时，慢指针落后快指针N；进入环之后，经过n-N次循环慢指针追上快指针。所以时间复杂度为n
24ms; 11.6%

优化：8ms；-1.56%

bool hasCycle(ListNode *head) { ListNode *slow = head; ListNode *fast = head; while (fast && fast->next){ slow = slow->next; fast = fast->next->next; if (slow == fast){ return true; } } return false; }

解法二：hash表-发生冲突即有环

待提交

时间复杂度：n，空间复杂度：n
待提交
总结： 【leetcode141-环形链表】1.c++中hashset和hashmap的基本操作
2.同一种解题思路的代码还可以大幅度优化——解法一优化之后性能提高了三倍！
原因分析：应该是因为优化前while中比较的为两个动态指针，优化之后while中比较的为一个动态指针。