链表：链表中环的入口节点

本文主要是介绍链表：链表中环的入口节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

解题思路
代码
总结

解题思路

根据题意，首先我们要判断链表中是否有环。
其次，根据环的特点，我们定义快慢双指针，向前移动，必然会有相遇的时候，相遇的节点正是需要求得链表中环的入口节点。
分两步：

求环中有多少节点。

定义双指针，前一个指针先走两步，后指针走一步，两个指针同时继续向前移动，如果链表有环，那么两个指针必然会相遇，返回一个环中的节点k
根据环的特性，沿着节点k向前移动，因为存在环，所以指针会重新回到k节点，这个探索的过程即可得到环的节点数目N。

求得环中双指针相遇的节点

定义快慢双指针，
快指针先走N步。
慢指针，快指针，同时向前移动。当两个指针相等的时候，则相遇，返回相遇节点即可。

代码

/*** 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 inLoop = getNodeInLoop(head);if(inLoop == null) {return null; // 判断链表是否有环。}int loopCount = 1;for(ListNode node = inLoop; node.next != inLoop; node = node.next){loopCount++; //统计环的节点数量。}ListNode fast = head;ListNode slow = head;for(int i = loopCount; i > 0; i--) {fast = fast.next;}while(slow != fast) {slow = slow.next;fast = fast.next;}return slow;}private ListNode getNodeInLoop(ListNode head) {if(head == null || head.next ==null) {return null;}ListNode slow = head.next;ListNode fast = slow.next;while (slow != null && fast != null) {if(slow == fast) {return slow;}slow = slow.next;fast = fast.next;if(fast != null) {fast = fast.next;}}return null;}
}