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

待提交

总结：

1.c++中hashset和hashmap的基本操作
2.同一种解题思路的代码还可以大幅度优化——解法一优化之后性能提高了三倍！
原因分析：应该是因为优化前while中比较的为两个动态指针，优化之后while中比较的为一个动态指针。