LeeCode 142 环形链表

142 环形链表

快慢指针

此题可以采用快慢指针的方法解决此问题。
快慢指针：

• 两个指针一快一慢，通过指针速度的差值来找到链表上的节点。
• 为什么快慢指针一定相遇： 因为快指针每次比慢指针快一步（每次都会追赶一步），如果有环，那么他俩早晚在环内相遇（慢指针进环时，比快指针相差的位置，就可以看快指针要追赶的步数）。
• 为什么相遇时慢指针一定没有走完一圈： 假设相遇时在x位置（x一定小于链表长度），此时就可以转换为快指针在一开始在慢指针后x个位置，所以经过x步后就会遇到慢指针（因为每步追赶1个位置），此时慢指针也走了x步（小于链表长度）。所以相遇时慢指针还没走一圈。（快指针就不一定走了多少圈）。

public class Solution {
    public ListNode detectCycle(ListNode head) {
    if(head == null || head.next == null ) {
    return null;}ListNode slow = head;ListNode fast = head;while(true) {
    if(fast == null || fast.next == null) {
    return null;}fast = fast.next.next;slow = slow.next;if(fast == slow) {
    break;}}fast = head;while(fast != slow) {
    fast = fast.next;slow = slow.next;}return fast;}
}