面试题56. 链表中环的入口结点

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

题目描述
一个链表中包含环，请找出该链表的环的入口结点。比如下面的链表，包含一个从3到5的环，3为这个环的入口节点，写个程序找到节点3。

这里写图片描述

思路：
本题可用快慢指针的思想。
设置两个指针p和q。p每次向前走一步，q每次向前走两步，即：p = p.next;q = q.next.next。
可以说p的速度是v，q的速度是2v。
因为q跑的快，所以会在某处追上p，这个位置记为：“meet处”（就是一个名字）。
设从起点到环入口处的长度为L1，环的长度为L2，环入口处到meet处的长度为L3（L3 <= L2）

接着做如下分析（可直接跳过看结论）：

算法分析：

这里写图片描述

从上面的分析可知 L1 = L2 - L3。
设置两个指针a，b，让a从起点处出发，b从“meet处”出发，ab的速度相同，则在相同时间内，a走过L1的距离，此时b一定是走过L2 - L3的距离，所以a，b最终会在环入口处相遇。

这里写图片描述

综上，算法的步骤如下：
Step1. 设置两个快慢指针，p，q。p每次向前走一步，q每次向前走两步，即：p = p.next ; q = q.next.next。
Step2. p、q向前走，直到相遇。相遇位置记为“meet处”。
Step3. 设置两个指针a，b。a从起点出发，b从“meet处”出发，直到相遇，相遇位置就是环的入口节点。

/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}
*/
public class Solution {public ListNode EntryNodeOfLoop(ListNode head) {ListNode entryNode = null;// Step1. 设置两个快慢指针，p，qListNode slow = head, fast = head, meet = null;// Step2. p、q向前走，直到相遇。相遇位置记为“meet处”。while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if(slow == fast) {meet = slow;break;}}// 设置两个指针a，b。a从起点出发，b从“meet处”出发，// 直到相遇，相遇位置就是环的入口节点。if(meet != null) {slow = head;fast = meet;while(slow != null && fast != null) {if(slow == fast) {entryNode = slow;break;}slow = slow.next;fast = fast.next;}}    }        return entryNode;}    
}