问题

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

Have you met this question in a real interview? Yes
Example
Given -21->10->4->5, tail connects to node index 1, return true

分析

请参阅 Intersection of Two Linked Lists(两个链表的交叉)

代码

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