企业官网建设流程全解析

国外哪些网站可以注册域名,基于php网站建设论文,网站ico在后台哪里找到,17173在线玩题目描述给定一个链表的头节点 head #xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#xff0c;评测系统内部…题目描述给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。示例 1输入head [3,2,0,-4], pos 1输出返回索引为 1 的链表节点解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2], pos 0输出返回索引为 0 的链表节点解释链表中有一个环其尾部连接到第一个节点。示例 3输入head [1], pos -1输出返回 null解释链表中没有环。提示链表中节点的数目范围在范围[0, 104]内-105 Node.val 105pos的值为-1或者链表中的一个有效索引解决方案这段代码的核心功能是在单链表中找到环形结构的入口节点若链表无环则返回nullptr是判断链表环的进阶问题依然采用「快慢指针」解法结合数学推导定位环入口时间复杂度O(n)、空间复杂度O(1)是该问题的最优解法。核心逻辑代码分两步完成先通过快慢指针判断是否有环并找到相遇点再利用数学规律定位环入口第一步找快慢指针相遇点慢指针slow、快指针fast均从表头出发慢指针每次走 1 步快指针每次走 2 步若链表有环快慢指针必会在环内相遇若快指针走到末尾fast或fast-next为空说明无环直接返回nullptr。第二步定位环入口相遇后将快指针fast重置到链表头节点且快指针改为和慢指针同速每次走 1 步快慢指针继续同步移动当二者再次相遇时相遇节点就是环的入口节点返回该节点即可。总结核心思路利用「快慢指针相遇」证明有环再通过「同速指针从头和相遇点出发必在环入口相遇」的数学规律定位入口关键规律设表头到环入口距离为a环入口到相遇点距离为b环长为c则相遇时快指针走的距离a n(bc) b是慢指针a b的 2 倍推导得a (n-1)c (c - b)即表头到入口的距离等于相遇点绕环到入口的距离效率优势全程仅用两个指针无额外空间开销时间复杂度O(n)是找环入口的最优解法。函数源码/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* slowhead; ListNode* fasthead; while(fast fast-next){ slowslow-next; fastfast-next-next; if(fastslow){ fasthead;//重置位置和速度 while(slow!fast){ fastfast-next; slowslow-next; } return slow; } } return nullptr; } };