LeetCode 141. Linked List Cycle

Problem

LeetCode 141. Linked List Cycle

1. 题目简述

给出一个链表，判断链表是否存在环。例如：

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

2. 算法思路

极其经典的老题目，类似题目：LeetCode 142. Linked List Cycle II

一种做法是用hashset来存储，每次遍历的时候去查找是否之前遍历过相同的点。这种方法看似简单，时间复杂度也不高，但是实际上调用contains函数次数也很多，时间反而较长。

这里我们使用双指针做法更好。

注意，2 pointers的代码要背下来，注意取while循环的方式，这个是死的。不要slow = head， fast = head.next，这样做步长就不是二倍关系，而是2倍-1，而且对于找入环点没有帮助。

双指针

两个指针，一个slow，一个fast，slow每次走一步，fast每次走两步，如果fast先到达null值，则说明无环，否则有环；如果slow和fast相遇，则说明有环。

时间复杂度:O(n)，无环的情况下自然不用多说，我们只考虑有环情况下的复杂度。如果有环，则slow进入环以后，fast可能在某位置，slow走一圈的时间，fast必定能走两圈，所以必定会相遇，而不是白绕很多圈，所以时间复杂度为O(n).

空间复杂度:O(1)，只有fast和slow两个指针变量。

/**
 * 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 slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }

        return false;
    }
}