题目描述：

判断有序list是不是环

要求：

时间复杂度o（n）

原文描述：

Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?

思路：

• 设置两个指针，一个快指针，每次走两步，一个慢指针，每次走一步
• 如果块指针==慢指针，那么包含环
• 注意判断空值和长度为一的情况
  -

代码：

/** * 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 fast = head;        ListNode slow = head;        while(fast.next != null && fast.next.next != null) {            fast = fast.next.next;            slow = slow.next;            if(slow == fast) {                return true;            }        }        return false;    }}

更多leetcode题目，请看我的leetcode专栏。链接如下：

我的微信二维码如下，欢迎交流讨论

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧，都是干货！

微信订阅号二维码如下：

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>