当前位置: 首页> 健康> 美食 > web用什么软件写_什么是web浏览器_seo推广小分享_列举五种网络营销模式

web用什么软件写_什么是web浏览器_seo推广小分享_列举五种网络营销模式

时间:2025/7/11 14:52:03来源:https://blog.csdn.net/zhouky1993/article/details/146450646 浏览次数:0次
web用什么软件写_什么是web浏览器_seo推广小分享_列举五种网络营销模式

题目:给一个链表的头节点head,返回链表进入循环的第一个节点,如果链表不是环形链表,返回null。

示例:

示例1:

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为1的节点

示例2:

输入: head = [1,2], pos = 0
输出: 返回索引为0的节点

示例3:

输入: head = [1], pos = -1
输出:  返回null

解题思路:此处需要用到快慢指针指针进行解题。

第一步:确定是否是环形链表。我们假设快指针一次走两步,慢指针一次走一步。如果链表是环形链表,那么只要时间足够,快慢指针一定会相遇;反之快指针将会走到头(即遇见null),且不会与慢指针相遇。

第二步:确定链表为环形链表后,寻找它的循环起始节点。

1)设链表头到环入口的距离为x,环入口到快慢指针第一次相遇点的距离为y,相遇点再到环入口的距离为z;所以环的总大小为 y+z 如图:

2)当快慢指针第一次相遇的时候,慢指针走过的路程 S(慢)= x+y;快指针可能已经在环内走过了N圈,所以快指针的路程 S(快)= x+y+N*(y+z);

3)路程 = 速度 * 时间,由于快指针的速度是慢指针的2倍,所以当时间一样时,快指针走过的路程时慢指针的2倍,即 2 * S(慢)= S(快),结合第二步我们得出 2 *(x+y)= x+y+N*(y+z);

4)化简得  x+y = N*(y+z) ;

5)移动y得: x= N*(y+z) -y;

6)从右侧取出1个y+z,得 x= (N-1)* (y+z) + (y+z)-y,

7)化简得到 x= (N-1)* (y+z) + z

8)上面式子可以看出,当N=1时,x=z;

9)由8可知,当我们将快慢指针中的一个指针(A)移动到head节点,另一个指针(B)继续指向快慢指针第一次相遇点,使两个指针同时以1的速度开始走,当B走完循环中剩下的路程z时,A刚好走完链表进入循环前的路程x,两指针相遇。

解题方法:

/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;//快指针当前非null,且下一步也非null,证明还未走完链表while (fast != null && fast.next != null) {//快指针速度为2fast = fast.next.next;//慢指针速度为1slow = slow.next;//快慢指针第1次相遇if (fast == slow) { //将慢指针指向headslow = head; while (fast != slow) { slow = slow.next;fast = fast.next;}//两指针第二次相遇,即x=z时return fast;}}//当快指针走完了链表,证明链表为非环形链表return null;}
}

关键字:web用什么软件写_什么是web浏览器_seo推广小分享_列举五种网络营销模式

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: