1. 首页
  2. 剑指offer经典面试题

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

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

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

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

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

若其中不包含环,则输出null

样例:

liwei201910117_1.png

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

则输出环的入口节点 3 。

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

liwei201910112_2.png

我写的错误解:

liwei20191019_3.png

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/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3272.html

« [剑指 Offer 第 2 版第 22 题] “链表中倒数第k个结点”做题记录.md
[剑指 Offer 第 2 版第 24 题] “反转链表”做题记录»

相关推荐

QR code