1. 题目描述2. 解题思路3. 代码实现
3.1 HashMap3.2 投机取巧3.3 HashSet3.4 快慢指针3.5 对比
1. 题目描述 2. 解题思路这个题目的常规思路应该也是很简单的，只需要遍历一下这一个链表，然后判断每一个节点是否在哈希表中：若不在则把遍历到的每一个链表都存储到一个哈希表当中，若在则表明先前已经遇到过这个节点了，即该链表存在回环，属于环形链表。哈希表可以采用HashMap或者HashSet。
做完了哈希表方法之后发现时间表现并不理想，于是开始寻找新的突破口。这时候我留意到题目说明中指出该链表的长度是在0到10000之间的，那不就意味着，只要我每一次迭代都取下一个节点，非环形链表最多只能迭代10000次，若10000次还没结束迭代，那么就代表是环形链表了。这个方法其实是有点投机取巧的，但时间性能表现确实比哈希表好多了。
最高效的思路应该是快慢指针了，类似龟兔赛跑的逻辑，让快指针每次走两步，慢指针每次走一步，快指针在慢指针前面，若不存在回环那么快指针最终就会等于null值，若存在回环，慢指针与快指针都进入“环”中后，快指针就变成了在慢指针的身后，当他们相遇时就可以判定存在回环了，因为不存在回环的话快指针永远比慢指针快，永远不会相遇。
3. 代码实现 3.1 HashMappublic boolean hasCycle(ListNode head) {
HashMap nodeMap = new HashMap<>();
while (head != null) {
if (nodeMap.get(head) != null)
return true;
nodeMap.put(head, "");
head = head.next;
}
return false;
}
3.2 投机取巧
public boolean hasCycle(ListNode head) {
for (int i = 0; i < 10000; i++) {
if (head == null)
return false;
head = head.next;
}
return true;
}
3.3 HashSet
public boolean hasCycle(ListNode head) {
HashSet
3.4 快慢指针
public boolean hasCycle(ListNode head) {
if (head == null)
return false;
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
slow = slow.next;
try {
fast = fast.next.next;
} catch (Exception e) {
return false;
}
}
return true;
}
3.5 对比
哈希表的方法其实已经是线性的时间复杂度O(n) 了，但由于哈希表存储查询也需要花费时间，因此时间性能不太理想，其空间复杂度也为O(n)。而投机取巧法的迭代次数为10000，因为n≤10000，因此也可以在一定程度上认为其时间复杂度是O(n)，并且只占用了一个循环变量的存储空间，其空间复杂度为O(1)。快慢指针的时间复杂度同样的O(n)，空间复杂度为O(1)。
但很神奇的一点是，明显哈希表的方法需要存储一整个哈希表并且的O(n) 的空间复杂度，但是为什么内存消耗却是最少的？只用一个循环变量的投机取巧法的内存消耗反而是最高的？甚是不解…
