Leetcode 141:Linked List Cycle python

题目

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.

解法1

构建一个seen列表，元素为node，如果当前node在seen中，则说明成环，否则整个链表结束都没有出现重复node则证明不成环。list的元素几乎可以是各种数据类型，甚至是类实例也可以。所以直接将node作为seen的元素即可。

class Solution(object):def hasCycle(self, head):""":type head: ListNode:rtype: bool"""seen = []while head:if head in seen:return Trueseen.append(head)head = head.nextreturn False

时间复杂度：O(N)
空间复杂度：O(N)

解法2

利用两个快慢指针，快指针每次走两步，慢指针每次走一步，如果整个链表访问结束没有出现快指针与慢指针重合的现象，则证明不成环，详细数学证明参考leetcode官方solution

class Solution(object):def hasCycle(self, head):""":type head: ListNode:rtype: bool"""if not head:return Falseslow = headfast = head.nextwhile slow!=fast:if not fast or not fast.next:return Falseslow = slow.nextfast = fast.next.nextreturn True

时间复杂度：O(N)
空间复杂度：O(1)

二刷解法

slow和fast的初始位置可以在同一个，这样同样可以检测环的存在，下面的代码看起来更舒服一些

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