No.141 Linked List Cycle

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

思路与想法：

This problem has two tags, linked list and two pointers, we can simply use two pointers to solve it. The slow one go one step each time and the fast one go two steps, if a linked list has a cycle, then these two pointers are supposed to meet in the cycle, otherwise, the fast one would become null as it goes to the end of the list.

2017.5.29

Solution:

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

Time Complexity:

O(n)