【剑指offer】链表找环的入口

快来打我* 2023-05-22 22:27 18阅读 0赞

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解题思路：

在链表判环的基础上进行优化

追击问题，一快一慢可以再环中相遇 p1=p1.next; p2=p2.next.next

那么如何找到环的入口

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NjAwMTM3_size_16_color_FFFFFF_t_70][]

针对一快一慢的节点，慢节点走的路成为s，则快的为2s，当两节点在环中环绕n圈

2s = s + nc

对于慢节点 s = a + x

两式子结合

a + x = nc

a = nc - x

a = (n-1)c + c-x

a = kc + (c-x)

我们可以看出 c-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
            if pHead == None or pHead.next == None:
                return None
            
            p1 = pHead
            p2 = pHead
            
            while True:
                if p1 == None or p2 == None:
                    return None
                p1 = p1.next
                p2 = p2.next.next
                if p1 == p2:
                    break
            
            if p1 == p2:
                pp = pHead
                while pp != p1:
                    pp = pp.next
                    p1 = p1.next
                return pp
            else:
                return None

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NjAwMTM3_size_16_color_FFFFFF_t_70]: /images/20230521/bcb258ebf2ae4896bc30421dda9e7961.png