python、js快慢指针解决环形链表问题
2022/7/1 14:21:59
本文主要是介绍python、js快慢指针解决环形链表问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
leetcode 241题,环形链表。https://leetcode.cn/problems/linked-list-cycle/
思路
1、哈希表
建立一个哈希表,每次访问的节点都存储起来。如果某个节点在哈希表中已存在,说明有环。时间复杂度O(n),空间复杂度o(n)
2、双指针之快慢指针
快指针每次移动2个节点,慢指针每次移动1个节点。如果有环,快指针会一直在环里,两个指针一定能相遇。反之无环,快指针会先到达终点。时间复杂度O(n),空间复杂度o(1)
实现
哈希表的实现比较简单,且空间复杂度高,此处仅给出更加合适的双指针代码。
python3
def has_cycle(head: Optional[ListNode]) -> bool: slow, fast = head, head # 快指针每次走两步,即fast.next.next。None没有next属性,所以当fast为None或者fast.next为None时,都会报错。 while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False
JavaScript
function hasCycle(head) { let slow = head; let fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow === fast) { return true; } else {}; // 此处是为了代码规范可读 }; return false; }
这篇关于python、js快慢指针解决环形链表问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-03-30[OIDC in Action] 2. 基于OIDC(OpenID Connect)的SSO(纯JS客户端)
- 2024-03-29terraform jsonencode
- 2024-03-13vuex-persist
- 2024-03-11icons for vue
- 2024-03-07breadcrumbs react js
- 2024-03-06react login page example
- 2024-03-06react router uselocation
- 2024-03-04postgres jsonb_set
- 2024-03-01react native uuid
- 2024-02-29vuejs sidebar