Given a linked list, determine if it has a cycle in it.
Given -21->10->4->5, tail connects to node index 1, return true
public boolean hasCycle(ListNode head)
1.O(n)空间。用HashSet，遍历链表的过程中，把结点加入到set里，如果遇到了碰到过的结点就说明有环。
2.O(1)空间。用快慢两指针。一个速度1(crt.next)，一个速度2(crt.next.next)，如果两者最后相遇说明一定是有环的。
1.HashSet实现
/** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } */ public class Solution { /* * @param head: The first node of linked list. * @return: True if it has a cycle, or false */ public boolean hasCycle(ListNode head) { // write your code here Set<ListNode> set = new HashSet<>(); while (head != null) { if (set.contains(head)) { return true; } set.add(head); head = head.next; } return false; } }
2.快慢指针实现
/** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } */ public class Solution { /* * @param head: The first node of linked list. * @return: True if it has a cycle, or false */ public boolean hasCycle(ListNode head) { // write your code here ListNode slow = head; ListNode quick = head; // 注意这个巧妙精简的写法，一旦出现null就肯定无环，正好借助它避免空指针 while (quick != null && quick.next != null && slow != null) { slow = slow.next; quick = quick.next.next; if (slow == quick) { return true; } } return false; } }
lintcode102- Linked List Cycle- medium
原文：http://www.cnblogs.com/jasminemzy/p/7859531.html