day23(力扣)环形链表(python实现)

- 日理万妓 2021-10-30 00:10 243阅读 0赞

题目描述：给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。  
示例 1：

输入：head = [3,2,0,-4], pos = 1
    输出：true
    解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
    输出：true
    解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
    输出：false
    解释：链表中没有环。

##  ##

分析：通过使用具有不同速度的快、慢两个指针遍历链表，空间复杂度可以被降低至 O(1)。**慢指针每次移动一步，而快指针每次移动两步**。如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 false。**现在考虑一个环形链表，把慢指针和快指针想象成两个在环形赛道上跑步的运动员（分别称之为慢跑者与快跑者）。而快跑者最终一定会追上慢跑者**。

代码：

# Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def hasCycle(self, head):
            """
            :type head: ListNode
            :rtype: bool
            """
            if head == None:
                return False
            p = head        #双指针定义
            q = head        #双指针定义
            
            while q:           #如果只有一个节点，则不可能成环
                if q.next ==None:
                    return False
                else:           #双指针快慢走
                    p = p.next
                    q = q.next.next
                    
                if p==q:        #如果二者可以相遇
                    return True
            return False

该题小编最早是在一本面经上看到的，上面解释道，环形链表题微软在面试的时候也曾使用过，当时小编觉得很新奇，因为题目新颖，并且当时小编没有任何思路，因此一直记忆犹新，看到本题的时候小编直接使用了双指针法进行解题，得到了正确的答案。