判断环形链表后，再继续使用指针跑。

    简单图示
    image.png

    严谨算法：
    image.png

    1. # 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 
    2. # 
    3. #  为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 
    4. # 
    5. #  说明：不允许修改给定的链表。 
    6. # 
    7. #  
    8. # 
    9. #  示例 1： 
    10. # 
    11. #  输入：head = [3,2,0,-4], pos = 1
    12. # 输出：tail connects to node index 1
    13. # 解释：链表中有一个环，其尾部连接到第二个节点。
    14. #  
    15. # 
    16. #  
    17. # 
    18. #  示例 2： 
    19. # 
    20. #  输入：head = [1,2], pos = 0
    21. # 输出：tail connects to node index 0
    22. # 解释：链表中有一个环，其尾部连接到第一个节点。
    23. #  
    24. # 
    25. #  
    26. # 
    27. #  示例 3： 
    28. # 
    29. #  输入：head = [1], pos = -1
    30. # 输出：no cycle
    31. # 解释：链表中没有环。
    32. #  
    33. # 
    34. #  
    35. # 
    36. #  
    37. # 
    38. #  进阶： 
    39. # 你是否可以不用额外空间解决此题？ 
    40. #  Related Topics 链表 双指针 
    41. #  👍 587 👎 0
    44. # leetcode submit region begin(Prohibit modification and deletion)
    45. # Definition for singly-linked list.
    46. # class ListNode(object):
    47. #     def __init__(self, x):
    48. #         self.val = x
    49. #         self.next = None
    51. class Solution(object):
    52.     def detectCycle(self, head):
    53.         """
    54.         :type head: ListNode
    55.         :rtype: ListNode
    56.         """
    57.         if not head or not head.next:
    58.             return None
    59.         fast, slow = head, head
    60.         while fast:
    61.             slow = slow.next
    62.             fast = fast.next
    63.             if fast:
    64.                 fast = fast.next
    65.             if fast == slow:
    66.                 break
    67.         # 如果没有环形节点
    68.         if fast != slow:
    69.             return None
    70.         # 如果有环
    71.         fast = head
    72.         while fast != slow:
    73.             fast = fast.next
    74.             slow = slow.next
    75.         return fast
    76. # leetcode submit region end(Prohibit modification and deletion)