Q141 Linked List Cycle

echobingo

发布于 2018-04-25 16:51:22

4860

发布于 2018-04-25 16:51:22

文章被收录于专栏：Bingo的深度学习杂货店Bingo的深度学习杂货店

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

解题思路：

首先，考虑了一种时间复杂度 O(n)，空间复杂度也为 O(n) 的方法。即用字典的键值保存已经出现过的地址。如果以后再出现该地址（dic.get[add] 为 True），则说明存在环。否则，不会有环。见Python实现1。

如果不使用额外的空间，即时间复杂度为 O(1)，没有想到方法。看到网上大神的思路，果然又是一道有技巧的题目。

如果有环，肯定从头到尾遍历链表是无法结束的，如图所示：

方法：定义两个指针，一个指针每次只走一步，另一个指针一次只走两步。如果有环，两个指针总会在某处相遇。如上图所示，如果两个指针都从1号结点出发，最后会在6号结点相遇。

网上也有证明的方法，这里略去。明白了这个技巧，则可以很容易实现，而且不会引入额外的空间，但是速度会比实现1慢一些。见Python实现2。

Python实现1：

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

# 方法1，空间复杂度 O(n)
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        add = {}
        cur = head
        while cur != None:
            if not add.get(cur):   # 判断键值是否存在的正确方法
                add[cur] = True
            else:
                return True  # 有环
            cur = cur.next
        return False  # 没有环

Python实现2：

# 方法2，空间复杂度 O(1)
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None:
            return False   # 没有环
        oneStep = twoStep = head
        while twoStep.next != None and twoStep.next.next != None:
            oneStep = oneStep.next  # 一次走一步
            twoStep = twoStep.next.next   # 一次走两步
            if oneStep == twoStep:  # 有环
                return True
        return False  # 没有环

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018.02.28 ，如有侵权请联系 cloudcommunity@tencent.com 删除

python

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

python

登录后参与评论

0 条评论

热度