【python-leetcode141-快慢指针】环形链表
【python-leetcode141-快慢指针】环形链表
西西嘛呦
发布于 2020-08-26 22:39:18
发布于 2020-08-26 22:39:18
问题描述：
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。核心思想：两个指针，一个走得慢，一个走得快，如果是有环的话，这两个指针迟早会相遇，否则快指针走到头了，则没有环。
这里有两种写法，第一种：
# 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:
if head == None or head.next == None:
return False
slow = head
fast = head.next
while slow != fast:
if fast == None or fast.next == None:
return False
slow = slow.next
fast = fast.next.next
return True结果：
第二种方式：
# 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:
if head == None or head.next == None:
return False
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
效率都好低，去跑了下leetcode排名第一的python算法，也是7.78%，那就不是代码的问题了。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-02-20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读