题目信息

• 链接: linked-list-cycle-ii

• Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

  There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

  Do not modify the linked list.

  Example 1:

  

  Input: head = [3,2,0,-4], pos = 1
  Output: tail connects to node index 1
  Explanation: There is a cycle in the linked list, where tail connects to the second node.
  
  

  Example 2:

  

  Input: head = [1,2], pos = 0
  Output: tail connects to node index 0
  Explanation: There is a cycle in the linked list, where tail connects to the first node.
  
  

  Example 3:

  

  Input: head = [1], pos = -1
  Output: no cycle
  Explanation: There is no cycle in the linked list.
  
  

  Constraints:

  • The number of the nodes in the list is in the range [0, 10<sup>4</sup>].
  • -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>
  • pos is -1 or a valid index in the linked-list.

  Follow up: Can you solve it using O(1) (i.e. constant) memory?

• 描述:

  • 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
  • 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
  • 不允许修改链表。

解题思路

• 使用与 Linked List Cycle 快慢指针相同的做法，fast和slow一起从head出发，fast每回合走2，slow每回合走1，当快慢指针第一次相遇的时候，将fast重置为初始head的位置，再继续以相同速度走，直到两个指针第二次相遇，其位置就是环开始的位置
  • Proof: 287 Find the Duplicate Number Floyd's Algorithm
• 示意图:
• 我们假设初始到环入口为a，入口到第一次相遇为b，第一次相遇到末尾为c
  • 对于slow而言，第一次相遇经过若干回合走了 a+b
  • 对于fast而言，第一次相遇经过若干回合走了n圈a+b+n(b+c)
  • fast一回合走2，slow一回合走1，所以设 x=a+b，2x = a+b+n(b+c), 即 a+b = n(b+c)
• 所以我们在相遇后让fast从头每回合走1，与slow再相遇在a的时候
  • fast从start开始走了a，刚好在环入口
  • 参照环入口位置，slow从距离环入口b的第一次相遇的位置又走了a，即相对于环入口位置来说走了: a+b=n(b+c)，刚好对于环入口点来说又走了n圈，还在环入口位置
  • 所以这个这样第二次相遇位置就是要找的环的入口

代码

  # 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]:
		  fast, slow = head, head
		  if head is None or fast.next is None:
			  return None
		  while fast is not None and slow is not None and fast.next is not None:
			  fast = fast.next.next
			  slow = slow.next
			  if slow == fast:
				  break
		  if slow != fast:
			  return None
		  else:
			  fast = head
			  while slow != fast:
				  slow = slow.next
				  fast = fast.next
			  return slow