141.Linked List Cycle

Tags: Easy Linked List

Links: https://leetcode.com/problems/linked-list-cycle/

---

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 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.

Example 2:

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

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:

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

---

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

        return false;
    }
};

快慢指针的思路，快指针每次走两步，慢指针一次走一步，如果有环则两个指针必相遇（两个指针的相对速度是1，所以肯定相遇，所以如果让快指针每次走n步， $n\geq2$，那么就可能不会相遇）。不会出现快指针访问不存在的区域，我们每次所做的都是在while的条件部分先判断后续区域是否可被访问，以此来做出保证。