题目描述:给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出 null。

Solutions

  其实这一个问题可以分解成三个子问题:

  1. 如何判断链表中是否包含环?
    • 两个指针,一个走一步,一个走两步,如果有环俩指针必相遇。
  2. 如何确定环中节点的个数?
    • 在 1 的基础上,从相遇点开始,一步一步走,边走边计数,回到当前结点时就走了一圈。
  3. 如何找到环的入口结点?
    • 在 1 的基础上,假设慢的指针走了 $x$ 步,那么快的指针走了 $2x$ 步,而多走的部分都是在环上走的,下面细说。

  基于上面的图,我们知道快指针慢指针多走了 x 步,多走的部分都是在环上走的,那么可以得到式子:

  慢指针走过的步数有可以表示为:

  集合上面两个式子可得:

  通过上面的式子我们知道,当从相遇点开始,我们重新找两个指针,一个在头节点位置,一个在相遇点,两个指针每次都走一步,这样的话肯定会在换入口处相遇。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        pSlow = pHead.next
        if pSlow is None:
            return None
        pFast = pHead.next.next
        
        b_loop = False
        while pSlow is not None and pFast is not None:
            if pSlow == pFast:
                b_loop = True
                break
            pSlow = pSlow.next
            if pSlow is None:
                return None
            pFast = pFast.next.next
        
        if not b_loop:
            return None
        
        pRestart = pHead
        
        while True:
            if pRestart == pSlow:
                return pRestart
            pRestart = pRestart.next
            pSlow = pSlow.next
# 运行时间:32ms
# 占用内存:5844k

References

  1. 056. 链表中环的入口结点
  2. 面试23题