这题从前校招的时候看面试宝典的时候就见到过。思想就是快慢指针。
- Use two pointers, walker and runner.
- walker moves step by step. runner moves two steps at time.
- if the Linked List has a cycle walker and runner will meet at some point.
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode walker = head ;
ListNode runner = head ;
while (runner.next !=null && runner.next.next != null){
walker = walker.next ;
runner = runner.next.next ;
if(walker == runner) return true ;
}
return false;
}
}
时间O(n)，空间O(1)。
这程序写起来有个注意点，就是while语句的判断，runner.next !=null && runner.next.next != null
这个条件是值得注意的，首先它是递进的，先判断runner.next再判断runner.next.next；其次它只判断runner不用判断walker，因为runner永远走在前面。我一开始写成walker.next !=null && runner.next.next != null这种是错的。
O(n)空间的方法
其实这道题的follow up说，能不能用一个不需要空间的方法？说明除了快慢指针还有其他方法的。搜索了一下，发现O(n)空间的方法是：
遍历链表，如果某个节点重复出现，那就是有环。
另外，对于有环我还有一些问题，比如1->2->1->2->3这样的单链表算不算有环？等等。
问了下师弟，师弟说我蠢。2怎么能既指向1又指向3呢？
这题在Java跟C里面有一些不一样。
这个O(n)空间的方法的描述应该是这样的：
从链表头开始遍历整个链表，并且记录已经遍历过的结点地址，如果发现有正在遍历的结点是已经遍历过的，则说明是存在环的。但是这种方式就需要使用额外的空间来存放遍历过的结点地址。
看清楚了，存放的是结点地址，而不是节点。在Java里面，虽然你可以生成同样value、同样next的结点，但是无法检查arraylist里面是否已经有这个结点的「地址」，不，我想了下，下面这个代码，list.contains检查的应该就是head的地址！：
public static boolean hasCycle(ListNode head) {
if (head == null) return false;
ArrayList<ListNode> list = new ArrayList<>();
while (head != null) {
if (list.contains(head)) {
return true;
}
head = head.next;
list.add(head);
}
return false;
}
test case这样写就行了：
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
n1.next = n2;
n2.next = n1;
但是上面这个方法的复杂度在leetcode中TLE了，不知是不是写的有问题。复杂度应该跟http://www.jianshu.com/p/52f9a3346a88 这个里面的一样的。
reference：
http://blog.sina.com.cn/s/blog_725dd1010100tqwp.html
http://www.programcreek.com/wp-content/uploads/2012/12/linked-list-cycle-300x211.png
