Python3解leetcode Linked List Cycle
2020-12-13 03:36
标签：没有 inf 列表 pytho node lin 还需 bool 最大值 问题描述： 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 Example 1: Example 2: Example 3: 思路1： 设置两个指针，一个每次走一步，一个每次走两步，那么如果有环，两个指针一定会相遇。 但这个代码写出来仅仅beats 28.6%，效率不高 代码1: 将上述思路优化后，代码如下： 思路2： 循环遍历整个列表，将遍历过的节点值设置为inf(最大值），如果后续遍历的节点值有等于inf的，则证明有环，否则就是没有环。 该算法写出来beats65.7%的人，还需要优化 代码2： Python3解leetcode Linked List Cycle 标签：没有 inf 列表 pytho node lin 还需 bool 最大值 原文地址：https://www.cnblogs.com/xiaohua92/p/11080739.htmlposwhich 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.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.
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
# 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 or head.next == None: return False
head2 = head
while head2.next != None and head.next != None:#当两个指针的next都不为None
if (head2.next.next != None):#如果走两步的指针head2的next.next不为None
head2 = head2.next.next
else:
return False
head = head.next
if(head == head2):
return True
return False
if not head or not head.next: return False
head2 = head
while not head2 and not head2.next:#只需要关注走的比较快的指针是否为空即可，若较快指针不为空，则较慢指针肯定不为空
head2 = head2.next.next
head = head.next
if(head == head2):
return True
return 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 or head.next == None: return False
head.val = float(‘inf‘)
while head.next != None:#当指针的next都不为None
if head.val == head.next.val:
return True
else:
head = head.next
head.val = float(‘inf‘)
return False
上一篇：力扣算法题—460LFU缓存
下一篇：json解析
文章标题：Python3解leetcode Linked List Cycle
文章链接：http://soscw.com/essay/27920.html