浙江商城网站建设,wordpress发表简短文字,建站快车登陆,广告推广免费前言: #x1f4a5;#x1f388;个人主页:Dream_Chaser#xff5e; #x1f388;#x1f4a5; ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上链表OJ题目 目录
leetcode142. 环形链表 II 1.问题描述 2.代码思路
3.问题分析 leetcode142. 环形链…前言: 个人主页:Dream_Chaser ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上链表OJ题目 目录
leetcode142. 环形链表 II 1.问题描述 2.代码思路
3.问题分析 leetcode142. 环形链表 II
来源: 142. 环形链表 II - 力扣LeetCode 1.问题描述 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null 题解接口 struct ListNode *detectCycle(struct ListNode *head) {} 2.代码思路 前提条件 是fast走的路程是slow的2倍。 解题思路: 第一步,先定义一个快指针fast以及一个慢指针slow,这里跟环形链表1的快慢指针的操作一致不作详细说明。之后找到可以证明链表带环的相遇点并定义meet指针指向slow或此时的fast。 第二步:接着让head指针从链表第一个节点开始移动meet指针从相遇点开始移动然后它们将会在链表带环的入口处相遇。(这是这道题思考的方向但是如何去证明呢) 代码实现: struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fasthead,*slowhead;while(fastfast-next){slowslow-next;fastfast-next-next;//带环(如果条件成立则证明该链表为带环链表)if(slow fast) {struct ListNode*meetslow; //求入环点 while(head!meet){headhead-next;meetmeet-next;}return meet;//返回链表开始入环的第一个节点}}return NULL;//如果链表无环则返回 null
} 代码执行: 3.问题分析 结论证明: 一个指针从相遇点(meet)走一个指针从链表头(head)开始走他们会在入口点(返回值)相遇。为什么?以下是证明: 假设: 链表头--环入口点距离:L 环入口点--相遇点距离:X 环的长度:C 依据题意求出slow指针所走过的距离明显是LX 然后思考一个问题:有没有可能slow进环转了几圈才追上? 答:不可能! 1圈之内fast必然追上slow因为他们之间距离每次缩小1不会错过slow走1圈fast都走了2圈了肯定追上了。 所以说可以简单的求出fast指针在环上走过的距离:LC X 并且根据 2*(LX) LCX LX C 第一种情况:LC-X --可以求出链表头到环入口点距离 试想一下,当L的距离越长环的大小越小那么LC-X依旧成立吗 由图可得, 可得到第二个结论:L(n-1)*CC-X (n-1)*C表示fast在环内转了n-1圈 总结:无论是第一种情况还是第二种情况meet与head均会在入环处相遇。 本篇到此结束感谢你的来访与支持如有错误十分欢迎指正。
