Given a linked list, determine if it has a cycle in it.
Example
Given -21->10->4->5, tail connects to node index 1, return true
Challenge
Follow up:
Can you solve it without using extra space?
思路
如果这个链表有环,那么如果两个人在环里走,一个快一个慢,快的人多跑一圈以后就会追上并且和慢的人重合。
Code
/** * 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 if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (slow == fast) { return true; } } return false; } }