题解 | #判断链表中是否有环#
判断链表中是否有环
http://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9
算法思想一：双指针
解题思路：
我们使用两个指针，fast 与 slow。
它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。
图解：
代码展示：
Python版本
class Solution: def hasCycle(self , head ): # write code here if not head: return head # 双指针 快慢指针 slow = head fast = head while slow and fast: slow = slow.next if fast.next: fast = fast.next.next else: return False # 当双指针相遇 即表示指针有环 if slow == fast: return True return False
复杂度分析：
时间复杂度O(N)：其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度
空间复杂度O(1)：额外使用的指针占用常数空间
算法思想二：哈希表
解题思路：
我们遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现
1、遍历链表，并将访问过的结点存储到哈希表中
2、判断结点是否在哈希表中，若存在则返回 true
3、遍历结束，则返回 false
代码展示：
JAVA版本
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode pos = head;
// 哈希表记录访问过的结点
Set<ListNode> visited = new HashSet<ListNode>();
while (pos != null) {
// 判断结点是否被访问
if (visited.contains(pos)) {
return true;
} else {
// 结点记录添加到哈希表中
visited.add(pos);
}
// 遍历
pos = pos.next;
}
return false;
}
} 复杂度分析：
时间复杂度O(N)：其中 N 为链表中节点的数目。遍历整个链表的结点
空间复杂度O(N)：其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。
投递华为等公司10个岗位 >
