JZ23链表中环的入口结点

JZ23链表中环的入口结点

思路:

采用双指针，设定快指针fast_p是慢指针slow_p的2倍，如果有环，则当两指针第一次相遇时慢指针一定不可能在环中走超过一圈，因此假设头结点到环的开头距离为a,环开头到第一次相遇节点的距离为b，第一次相遇到环开头距离为c，因此快指针fast_p走过的距离=a + (b+c)k +b (k为大于1的正整数)，慢指针slow_p走过的距离= a + b 因为快指针走过的路程是慢指针的两倍，则有 (a+b)2 = a+(b+c)k+b 化简得 a = (k-1)(b+c) +c （k-1是大于0的整数）,此时让快指针从头和慢指针同样速度前进，两指针第一次相遇必在环的入口结点

如图：

代码如下：

class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        fast_p = pHead
        slow_p = pHead
        while True:
            if not fast_p or not fast_p.next :
                return None
            slow_p = slow_p.next
            fast_p = fast_p.next.next         
            if slow_p == fast_p:
                fast_p = pHead
                while fast_p != slow_p:
                    fast_p = fast_p.next
                    slow_p = slow_p.next
                return fast_p
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16