本文共 1816 字，大约阅读时间需要 6 分钟。

141. 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 = 1Output: trueExplanation: There is a cycle in the linked list, where tail connects to the second node.

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

Solution

Hash Table

Runtime: 24 ms, faster than 10.66% of C++ online submissions for Linked List Cycle.

class Solution {   public:    bool hasCycle(ListNode *head) {           if(head == NULL) return false;        unordered_map
   
     map;        for(ListNode* p = head; p != NULL; p = p->next){               if(map[p]) return true;             map[p] = p;        }        return false;    }};
   

边建表，边查找。如果之前已经创建过映射，那么说明有Cycle。

Two Pointers

Runtime: 12 ms, faster than 51.39% of C++ online submissions for Linked List Cycle.

class Solution {   public:    bool hasCycle(ListNode *head) {           if(head == NULL || head->next == NULL) return false;        ListNode* fast = head->next;        ListNode* slow = head;        while(fast != slow ){               if(fast == NULL || fast->next == NULL || slow == NULL) return false;            else{                   slow = slow->next;                fast = fast->next->next;            }        }        return true;    }};

利用快慢指针：两个不同前进速度的指针，可以假设一个步进为1，一个步进为2。