【图解】快慢指针找单链表中环的起点

在【图解】快慢指针解链表判环问题中，我们学会了判断单链表中是否有环，已经有环的情况下判断环的长度。在实际面试中，面试官还可能让我们进一步找到环的起点。这就是我们今天的问题啦。

1 问题描述

给定一个包含一个环的单链表，写一个函数，找到环的起始节点。

下图中，Cycle start就是我们要找的节点：

2 问题分析

利用【图解】快慢指针解链表判环问题中的技术，我们可以找出环的长度，然后，我们就可以按照下面的步骤来找到环的起点：

• 定义两个指针，不妨叫p1和p2
• 将它们初始化指向链表的开始节点
• 找到环的长度，不妨设为L
• 将p2向前移动L个节点
• 同步移动p1和p2，直到它们相遇
• 因为p2比p1超前了L个节点，当p1和p2相遇时，p2应该是刚好绕环一周，所以p1和p2相遇的节点就是环的起点

具体可以参考如下图示：

3 代码实现

from __future__ import print_function


class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next

  def print_list(self):
    temp = self
    while temp is not None:
      print(temp.value, end='')
      temp = temp.next
    print()


def find_cycle_start(head):
  cycle_length = 0
  slow, fast = head, head
  while (fast is not None and fast.next is not None):
    fast = fast.next.next
    slow = slow.next
    if slow == fast:  # 找到环
      cycle_length = calculate_cycle_length(slow)
      break
  return find_start(head, cycle_length)


def calculate_cycle_length(slow):
  current = slow
  cycle_length = 0
  while True:
    current = current.next
    cycle_length += 1
    if current == slow:
      break
  return cycle_length


def find_start(head, cycle_length):
  pointer1 = head
  pointer2 = head
  # 将 pointer2 前移 'cycle_length' 个节点
  while cycle_length > 0:
    pointer2 = pointer2.next
    cycle_length -= 1
  # 同步前进，直到相遇
  while pointer1 != pointer2:
    pointer1 = pointer1.next
    pointer2 = pointer2.next
  return pointer1