环形链表 https://leetcode-cn.com/problems/linked-list-cycle/

https://www.cxyxiaowu.com/647.html

设置两个指针，一个每次走一步的慢指针和一个每次走两步的快指针。

如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环

如果含有环，快指针会超慢指针一圈，和慢指针相遇，说明链表含有环。

python

python
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  #空链表 或者 链表元素个数小于等于2
        #快慢指针
        slow = head
        fast = head.next
        while slow != fast:
            if not fast or not fast.next:  #快指针遇到null
                return False
            slow = slow.next
            fast = fast.next.next
        return True
a=ListNode(1)
b=ListNode(2)
c=ListNode(3)
d=ListNode(4)
a.next=b
b.next=c
c.next=d
d.next=b
print(Solution().hasCycle(a))

python
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 None  # 空链表 或者 链表元素个数小于等于2
        # 快慢指针
        slow = head
        fast = head
        while (fast is not None):
            slow = slow.next
            if (fast.next is None):
                return None
            fast = fast.next.next
            if fast is slow:
                ptr = head
                while (ptr is not slow):
                    ptr = ptr.next
                    slow = slow.next
                return ptr
        return None
a = ListNode(1)
b = ListNode(2)
c = ListNode(3)
d = ListNode(4)
a.next = b
b.next = c
c.next = d
d.next = b
print(Solution().detectCycle(a).val)