一、题目
二、示例
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。
三、思路
本题是在环形链表的基础上,进行改进,然后返回环形链表的起始位置的节点即可。本题涉及到数学知识,此时我们先画一个简易的图。
如图所示,AB为x, BC为t, CB为w,假设在C点处相遇,我们如果要相遇则必须满足如下关系式:
2 * (x + t) = x + (t + w) * n + t
此时假设n为1, 带入可知。
x = w
所以当我们使用快慢指针让两者第一次相遇的时候,此时让快指针指向head
,然后每一次走一步,当两者再次相遇时,此时该节点就是其实点。
四、代码
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
if( !head || !head.next) return null
let slow = head
let fast = head
while(slow && fast && fast.next) {
slow = slow.next
fast = fast.next.next
if(slow === fast) {
break
}
}
fast = head
while(slow && fast) {
if(slow === fast) {
return fast
}
slow = slow.next
fast = fast.next
}
return null
};
五、总结
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_47450807/article/details/123446476
内容来源于网络,如有侵权,请联系作者删除!