题目:给一个链表的头节点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) {
- //快指针速度为2
- fast = fast.next.next;
- //慢指针速度为1
- slow = slow.next;
- //快慢指针第1次相遇
- if (fast == slow) {
- //将慢指针指向head
- slow = head;
- while (fast != slow) {
- slow = slow.next;
- fast = fast.next;
- }
- //两指针第二次相遇,即x=z时
- return fast;
- }
- }
- //当快指针走完了链表,证明链表为非环形链表
- return null;
- }
- }
复制代码
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |