链表环的问题

1. 给定一个链表，判断链表中是否有有环
2. 求环的入口
3. 求环的大小
4. 链表倒数第k个节点
5. 链表的中间节点

1. 如何判断链表有环？

快慢指针，慢指针速度为1（步长为1遍历节点），快指针速度为2。
如果链表没有环，那么快指针为None，就结束了。
如果链表有环，快指针不会为None，会一直环中循环下去；那么慢指针总会进入环。当快慢指针都在环中，二者相对速度（慢指针相当于不动，快指针相对速度为1）为1，那么快指针就会不断逼近慢指针，直至相遇。
https://leetcode-cn.com/problems/linked-list-cycle/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                break
        return slow is fast

2. 如何判断环的入口？

https://leetcode-cn.com/problems/linked-list-cycle-lcci/

快慢两指针相遇，那么快指针所走的路程S1 是 慢指针所走路程S2 的 2倍。

进一步化简，得

从链表头到环入口的距离是：L
从相遇点P到环入口的距离是：H - x
因此，两个指针以同样的速度1，分别从链表头和相遇点出发，第一次相交的位置就是环入口。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        if fast != slow: # 这个判断必须加 因为上面循环跳出也可能是循环体结束了导致的
            return
        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        return slow

3. 求环的大小

找到入口后，入口处设定一指针，另外一指针在环中跑一圈同时计数，直到两指针相交。

4. 链表倒数第k个节点

https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/submissions/
注意边界条件，k如果大于链表的长度或者等于0。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        # 快慢指针
        # fast_ptr = head
        if head.next is None or k == 0:
            return head
        slow_ptr = head
        i = 0
        while head is not None:
            if i < k:
                # fast_ptr = fast_ptr.next
                i += 1
            else:
                # fast_ptr = fast_ptr.next
                slow_ptr = slow_ptr.next
            head = head.next
        return slow_ptr if i == k else None

5. 链表的中间节点

https://leetcode-cn.com/problems/middle-of-the-linked-list/submissions/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        if head is None:
            return None
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow