题目描述:
给定一个链表, 返回链表开始入环的第一个节点. 如果链表无环, 则返回 null.
为了表示给定链表中的环, 我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始). 如果 pos 是 -1, 则在该链表中没有环.
说明: 不允许修改给定的链表.
分析
给出示意图:
对符号的一些说明:
公式演算:
很容易得到:
m=x+y(环的长度两种表示形式);
快指针走两步, 慢指针走一步. 所以快指针的速度是慢指针的速度的二倍, 所以相同时间内, 快指针走的长度也是慢指针走的长度的二倍:
有: f=2s;
在快指针走过 圈后两指针相遇, 有: m+kn+y=2(m+y);
去括号后有: m+kn=2m+y;
解得: m=kn-y;
又因为: n=x+y;
所以有: m=kn-(n-x);
所以: m=x+n(k-1).
m 是头节点到环起点的长度;
x 是相遇点到头节点的长度;
x-m 是 (k-1) 个环的长度.
通过公式的演算, 我们能够明白:
找到相遇点后, 链表头节点与相遇点节点同时出发, 相遇处便是环的起点. 相遇点节点多走了 (k-1) 个环.
- /**
- * 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) {
- if(head==null)
- return null;
- ListNode slow = head;
- ListNode fast = head;
- while(fast != null && fast.next != null){
- slow = slow.next;
- fast = fast.next.next;
- if(slow == fast){
- break;
- }
- }
- if(fast == null || fast.next == null)
- return null;
- fast = head;
- while(slow != fast){
- fast = fast.next;
- slow = slow.next;
- }
- return slow;
- }
- }
对代码的解释:
1, 如果 head 是空, 则不存在环, 直接返回 null;
2, 设置快慢指针开始均指向 head, 设置循环条件, 快指针不为空且快指针的 next 域指向的不为空进入循环, 其中空指针的 next 域的指向不为空保证快指针可以走两步, 否则有可能出现空指针异常;
3, 如果快慢指针指向相同节点, 则 break 掉, 是相遇点;
4, 第一次循环过后, 如果 fast 为空或者 fast.next 为空, 则不存在环, 返回 null;
5, 如果存在环, 让 fast 指针从开始移动, slow 指针从相遇点移动, 相遇则为起点, 将其 return 即可.
来源: http://www.bubuko.com/infodetail-3393721.html