[剑指 Offer 第 2 版第 23 题] “链表中环的入口结点”做题记录

第 23 题：链表中环的入口结点

传送门：AcWing：链表中环的入口结点，牛客网 online judge 地址。

给定一个链表，若其中包含环，则输出环的入口节点。

若其中不包含环，则输出null。

样例：

给定如上所示的链表：[1, 2, 3, 4, 5, 6]，编号：2。 注意，这里的 2 表示编号是 2 的节点，节点编号从 0 开始。所以编号是 2 的节点就是 val 等于 3 的节点。

则输出环的入口节点 3 。

分析：看的答案，记住结论就好，编码上还是要注意特判的情况，还有空指针的情况。“慢”指针进入环的时候，“快指针”要来追它，因为快慢指针走的步数差是固定的。例如： A 手上有 100 块钱，A 每天赚 10 块钱，B 手上有 50 块钱，B 每天赚 20，一定有一天，你们的钱相等，而且只要环内结点个数这么多就可以了。

我写的错误解：

Python 代码：

  # 34. 链表中环的入口结点
    # 给定一个链表，若其中包含环，则输出环的入口节点。
    #
    # 若其中不包含环，则输出null。

    # Definition for singly-linked list.
    class ListNode(object):
        def __init__(self, x):
            self.val = x
            self.next = None


    class Solution(object):
        def entryNodeOfLoop(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            # 先考虑边界情况
            if head is None or head.next is None:
                return None

            slow = head
            fast = head

            while fast and fast.next:
                # 慢指针走一步，快指针走两步
                slow = slow.next
                fast = fast.next.next
                if slow == fast:
                    # 说明链表中存在环
                    break

            # 注意：跳出循环的原因有两个，有可能是根本没有环，即上面  while fast and fast.next 不成立
            # 也有可能是 slow == fast 里 break 的，分别讨论就可以了
            if fast is None or fast.next is None:
                return None

            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            # 走到这里，说明 slow == fast
            return slow

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/