题解 | #链表中环的入口结点#

链表中环的入口结点

http://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4

方法一 :用列表,当节点重复存在于列表时,则说明是环的入口
方法二:快慢指针 第一次相遇时,其中一指针保持在原来的地方,另一指针回头部,同时逐步遍历,再次相遇的地方就是环的入口
# 找到链表中的环的入口
    def EntryNodeOfLoop(self, pHead : ListNode):
        # write code here
        # 方法一 :用列表,当节点重复存在于列表时,则说明是环的入口
        ls = []
        while pHead:
            if ls.__contains__(pHead):
                return pHead
            ls.append(pHead)
            if pHead.next:
                pHead = pHead.next
            else:
                return None
        return None

        # 方法二:快慢指针 第一次相遇时,其中一指针保持在原来的地方,另一指针回头部,同时逐步遍历,再次相遇的地方就是环的入口
        sNode = self.hasCycle(pHead)
        if sNode == None:
            return None

        fNode = pHead
        while fNode != sNode:
            fNode = fNode.next
            sNode = sNode.next
        return fNode
    
    def hasCycle(self, pHead : ListNode):
        if not pHead:
            return None
        fNode = pHead
        sNode = pHead
        while fNode and fNode.next:
            fNode = fNode.next.next
            sNode = sNode.next
            if fNode == sNode:
                fNode = pHead
                return sNode
        return None


全部评论

相关推荐

码农索隆:这种hr,建议全中国推广
点赞 评论 收藏
分享
白火同学:能。我当初应届沟通了1200,收简历50,面试10左右吧,加油投吧
投了多少份简历才上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务