【算法日常】判断环形链表

佚名 5年前 (2019-12-09) 算法 1121人围观抢沙发百度已收录

环形链表

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

目前考虑到两种解法，但都需要辅助空间，第一种 O(n) 第二种 O(1)

第一种借助辅助字典进行判断

将走过的节点都记录在字典中，通过查询字典的key值是否存在来确定是否有环
时间复杂度为 O(n) , 空间复杂度为 O(n)

代码如下：

# -*- coding: utf-8 -*- # @Author : xaohuihui # @Time : 19-12-6 # @File : detect_cycled.py # Software : study """ 检测环形链表 """ class ListNode: def __init__(self, x): self.val = x self.next = None def has_cycle(head: ListNode) -> bool: dict_node = dict() i = 0 if head and head.next: while head and head.next: id_head = str(id(head)) if dict_node.get(id_head) is None: dict_node[id_head] = i else: return True i += 1 head = head.next return False else: return False if __name__ == '__main__': # head=[3,2,0,4] pos= 1 node1 = ListNode(3) node2 = ListNode(2) node3 = ListNode(0) node4 = ListNode(4) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node2 print(has_cycle(node1))

输出如下：

True

第二种解法快慢指针

# -*- coding: utf-8 -*- # @Author : xaohuihui # @Time : 19-12-6 # @File : detect_cycled.py # Software : study """ 检测环形链表 """ class ListNode: def __init__(self, x): self.val = x self.next = None # 第二种解法 def has_cycle(head: ListNode) -> bool: if head and head.next: fast = slow = head while fast and fast.next: slow = slow.next fast = fast.next.next if fast == slow: return True else: return False if __name__ == '__main__': # head=[3,2,0,4] pos= 1 node1 = ListNode(3) node2 = ListNode(2) node3 = ListNode(0) node4 = ListNode(4) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node2 print(has_cycle(node1))