141. Linked List Cycle判断链表中是否存在回路Python

给定一个链表,确定其中是否有循环。

为了表示给定链表中的循环,我们使用一个整数pos来表示尾部连接到的链表中的位置(0索引)。如果pos-1,则链接列表中没有循环。要求时间复杂度为O(1)

Input:  [1,2,3,4] pos:1 《141. Linked List Cycle判断链表中是否存在回路Python》

Output: True

Input: [1,2,3] pos:-1《141. Linked List Cycle判断链表中是否存在回路Python》

Output: Flase.

定义一个i(每次运行下一个)和一个j(隔一个一运行),当他们相遇的时候就证明有环。用i is j返回bool,如果用i==j因为returnTrue,所以都一样。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        i=j=head 
        while i and j and j.next:
            i=i.next
            j=j.next.next
            if i is j:
                return True
        return False
    原文作者:weixin_...
    原文地址: https://blog.csdn.net/weixin_44516745/article/details/106309797
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞