【leetcode】141. 环形链表 「爱情、让人受尽委屈。」 2022-03-16 06:56 190阅读 0赞 题目描述: 给定一个链表,判断链表中是否有环。 有返回True,无返回False。 示例: > 有环示例: > ![20190226214956725.png][] 链接:[https://leetcode-cn.com/problems/linked-list-cycle/][https_leetcode-cn.com_problems_linked-list-cycle] **由于原题描述容易让人对输入的内容造成误解,所以我做了删减后贴在这里。** -------------------- 第一种:利用集合记录访问过的结点元素。 class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ record = set() while head: if head in record: return True record.add(head) head = head.next else: return False 第二种:思路出自一网友,我结合Python的语言特性有了以下方法。 class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ # 利用Python语言的特性 while head: if not hasattr(head, "visited"): head.visited = True head = head.next else: return True else: return False 第三种:设置快慢指针,如果链表有环,快慢指针总会相遇。 class SolutionThird(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ # slow 慢指针;fast 快指针 slow = fast = head while fast and fast.next: # 慢指针每次前进一个结点 # 快指针每次前进两个结点 slow, fast = slow.next, fast.next.next if slow is fast: return True else: return False [20190226214956725.png]: /images/20220316/14bea879bdd841e4a240224fa61e54c7.png [https_leetcode-cn.com_problems_linked-list-cycle]: https://leetcode-cn.com/problems/linked-list-cycle/
还没有评论,来说两句吧...