leetcode环形链表_python

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leetcode环形链表_python，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1616字，纯文字阅读大概需要3分钟。

内容图文

141环形链表
方法一：快慢指针。
分析：很显然，答案有两种情况，有环，无环。分别设置快慢指针，有环：必然相交，返回True，无环：快指针指向NULL,返回False。

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None:
            return False
        low = head
        high = head
        while high != None and high.next != None:  #这里应该是and,注意这里的判断顺序不能改变
            low = low.next 
            high = high.next.next
            if low == high:
                return True
        return False        

方法二：利用集合
分析：依次将节点放入集合内，如果存在重复元素，证明有环，返回True；否则，无环，返回False。

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        map = {}
        while head:
            if head in map:
                return True
            else:
                map[head] = 'point'
            head = head.next
        return False

142 环形链表 II
方法1：快慢指针。
第一次做的时候也是一脸懵逼，根本不知道哪里下手。后来看了人家的分析才写出来的。遇到这种题多分析，多尝试。关键还是相交点的分析。
我考虑一下简单的情况，只是为了方便大家理解。

根据上图的简单计算，当有环的情况下，可以采用方法：第一次相交后，让fast = head ,fast = fast.next.当第二次相交时，该节点就是第一次入环节点。

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow = head
        fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                fast = head
                while fast != slow:
                    fast = fast.next
                    slow = slow.next
                return slow
        return None

方法二：利用集合
思路很简单，返回第一个重复元素，如果没有返回NULL

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        map = {}
        while head:
            if head in map:
                return head
            else:
                map[head] = 'zzt'
            head = head.next
        return None

内容总结

以上是互联网集市为您收集整理的leetcode环形链表_python全部内容，希望文章能够帮你解决leetcode环形链表_python所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端