Leetcode No.141 Linked List Cycle环形链表(c++实现)
2021/8/11 20:08:35
本文主要是介绍Leetcode No.141 Linked List Cycle环形链表(c++实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1. 题目
1.1 英文题目
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
1.2 中文题目
给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。为了表示给定的环,我们使用整数pos来表示链表尾连接到链表中的位置(索引从0开始)。如果pos是-1,则在该链表中没有环。注意:pos不做为参数进行传递,仅仅是为了表示链表的实际情况,pos为-1或者链表中的一个有效索引
如果链表中存在环,则返回true,并返回环入口在链表中的位置、环的周长。否则,返回false。
1.3输入输出
输入 | 输出 |
---|---|
head = [3,2,0,-4], pos = 1 | true |
head = [1,2], pos = 0 | true |
head = [1], pos = -1 | false |
1.4 约束条件
- The number of the nodes in the list is in the range [0, 104].
- -105 <= Node.val <= 105
- pos is -1 or a valid index in the linked-list.
2. 分析
2.1 快慢指针法
代码如下:
class Solution { public: bool hasCycle(ListNode* head) { ListNode* faster = head;//慢指针 ListNode* slower = head;//快指针 while (faster != nullptr && faster->next != nullptr) { faster = faster->next->next;//快指针一次走两步 slower = slower->next;//慢指针一次走一步 if (faster == slower) {//快慢指针相遇,说明存在环 return true; } } return false;//不存在环的情形 } };
参考:https://leetcode.com/problems/linked-list-cycle/discuss/44604/My-faster-and-slower-runner-solution
这篇关于Leetcode No.141 Linked List Cycle环形链表(c++实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置