Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?
给定一个链表，判断链表中是否有环。
进阶： 你能否不使用额外空间解决此题？
代码语言：javascript复制/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode runner = head;
ListNode walker = head;
while (runner.next != null && runner.next.next != null) {
runner = runner.next.next;
walker = walker.next;
if (runner == walker) return true;
}
return false;
}
}如果头结点为空或者只有一个结点，肯定不存在环。
定义2个指针，一个每次走2步，一个每次走1步，如果前面的指针走到了末尾，肯定不存在环，有环到不了null情况。
如果有环，那么前面的指针一定在这个环里转圈，后面的指针也会走到这个环里来，他们一定会相遇，此时跳出循环返回true。
