安卓盒子做网站,网站建设费用计入固定资产,南宁网站制作计划,wordpress getthetags题目 给你一个链表的头节点 head #xff0c;判断链表中是否有环。如果存在环 #xff0c;则返回 true 。 否则#xff0c;返回 false 。 如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#xf…题目 给你一个链表的头节点 head 判断链表中是否有环。如果存在环 则返回 true 。 否则返回 false 。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 示例
输入head [3,2,0,-4], pos 1
输出true
解释链表中有一个环其尾部连接到第二个节点。 快慢指针法 快慢指针法也叫Floyd判圈法是解决链表中环检测问题的经典算法。其核心思想是使用两个指针一个快指针每次移动两个节点一个慢指针每次移动一个节点。如果链表中存在环快慢指针最终会在环中的某一点相遇。若不存在环快指针会先到达链表尾部。使用快慢指针法求解本题的主要步骤如下。 1、初始化指针。开始时定义两个指针一个快指针fast和一个慢指针slow均指向链表的头节点。 2、移动指针。每次迭代时慢指针slow向前移动一步快指针fast向前移动两步。如果链表中存在环由于快指针移动速度是慢指针的两倍最终快指针会追上慢指针。 3、终止条件。如果链表中没有环快指针会首先到达链表的尾部None这时可以确定链表无环。相反如果快慢指针相遇则表明链表中存在环。 根据上面的算法步骤我们可以得出下面的示例代码。
class ListNode:def __init__(self, x):self.val xself.next Nonedef create_linked_list(length, pos -1):if length 1 or (pos ! -1 and (pos 0 or pos length)):return Nonehead ListNode(0)current headcycle_node Nonefor i in range(1, length 1):new_node ListNode(i)current.next new_nodecurrent new_nodeif i pos 1:cycle_node new_node# 只有当pos有效且不为-1时才创建环if cycle_node:current.next cycle_node# 返回真正的头节点忽略初始的0节点return head.nextdef has_cycle_fast_slow_pointer(head):if head is None or head.next is None:return Falseslow headfast head.nextwhile fast is not None and fast.next is not None:if slow fast:return Trueslow slow.nextfast fast.next.nextreturn False# 创建有环链表
head_with_cycle create_linked_list(4, 1)
# 输出: True
print(has_cycle_fast_slow_pointer(head_with_cycle))# 创建无环链表
head_no_cycle create_linked_list(4, -1)
# 输出: False
print(has_cycle_fast_slow_pointer(head_no_cycle)) 哈希表法 哈希表法利用数据结构中的哈希表来记录每个访问过的节点。由于哈希表的查找效率非常高平均时间复杂度为O(1)故我们可以在遍历链表的同时将每个访问过的节点添加到哈希表中。当发现某个节点已经被访问过即该节点存在于哈希表中时则可断定链表中存在环。使用哈希表法求解本题的主要步骤如下。 1、初始化。创建一个空的哈希表在Python中通常是集合set。 2、遍历链表。从链表头开始遍历对于每一个访问到的节点执行以下操作。 1检查当前节点是否已经在哈希表中。 2如果不在将当前节点添加到哈希表中并继续遍历下一个节点。 3如果在哈希表中发现了当前节点说明存在环直接返回True。 3、遍历结束。如果遍历完整个链表都没有发现重复的节点则说明链表中没有环返回False。 根据上面的算法步骤我们可以得出下面的示例代码。
def has_cycle_hashset(head):visited_nodes set()while head is not None:# 如果节点已经在集合中说明有环if head in visited_nodes:return Truevisited_nodes.add(head)head head.next# 遍历结束没有发现环return False# 创建有环链表
head_with_cycle create_linked_list(4, 1)
# 输出: True
print(has_cycle_hashset(head_with_cycle))# 创建无环链表
head_no_cycle create_linked_list(4, -1)
# 输出: False
print(has_cycle_hashset(head_no_cycle)) 总结 快慢指针法不需要额外的空间时间复杂度为O(n)其中n是链表中的节点数量。哈希表法则提供了另一种思路虽然它需要额外的O(n)空间但优点是实现直观易于理解和编码。 在实际应用中如果对空间复杂度有严格要求推荐使用快慢指针法。如果空间不是问题而对代码的简洁性和直观性有更高要求哈希表法也是一个不错的选择。 如果想阅读最新的文章或者有技术问题需要交流和沟通可搜索并关注微信公众号“希望睿智”。
