【重点】剑指offer——面试题56：链表中环的入口

力扣141和142分别是判断是否有环及环入口。
一个很好的解释：https://www.cnblogs.com/songdechiu/p/6686520.html

链表是否有环

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
        slow = fast = head
        while slow and fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

Java

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }

        return false;
    }
}

链表环入口

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        if not fast or not fast.next: # 注意这个判断条件！！！
            return None
        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        
        return slow

Java

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, 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;
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }
}

##Solution1:
非常经典的快慢指针套路题。下面这个链接讲解的很详细。其实问题的关键在于为什么快指针的速度一定是慢指针的2倍，3倍或4倍行不行？？
快慢指针是一类很经典的算法，在这里贴一个讲解的比较清楚的博客：
https://www.cnblogs.com/songdechiu/p/6686520.html

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(pHead == NULL || pHead->next == 0 || pHead->next->next == 0)
            return NULL;
        struct ListNode *slow = pHead->next, *fast = pHead->next->next; //slow走了1步到pHead->next的位置，fast走了2步
        while(fast != slow) {                                           //到了pHead->next->next的位置
            if(fast->next != NULL && fast->next->next != NULL) {
                slow = slow->next;
                fast = fast->next->next;
            }
            else 
                return NULL;
        }
        struct ListNode *temp = pHead;
        while(temp != slow) {
            temp = temp->next;
            slow = slow->next;
        }
        return temp;
    }
};

##关于快指针速度的解释
https://blog.csdn.net/xgjonathan/article/details/18034825