博文中会简要介绍Leetcode P0141题目分析及解题思路。

“Linked List Cycle”这道题是比较经典的双指针问题。虽然我们可以使用HashTable来记录每一个访问的结点，但是这样一来空间复杂度就是O(n)，会使用较多的空间。除了这个解法外，我们可以采取双指针的方法来解决这道题。

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

采用双指针的解法其实非常简单，用快慢指针即可，慢指针每次走一个结点，快指针每次走两个结点，如果最终快慢指针能够相遇，即快指针追上了慢指针，说明有环，否则无环。

以下是Java的题解代码实现。

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

以下是C++的题解代码实现。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head)
            return false;
        
        ListNode *slow = head, *fast = head->next;
        while (fast && fast->next && fast != slow) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        return (fast == slow);
    }
};