Q141 Linked List Cycle

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  # 没有环

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏蜉蝣禅修之道

LeetCode之Intersection of two linked list不同方法

1092
来自专栏大数据学习笔记

Java程序设计(Java9版):第2章 数据类型与运算符(Data types and Operators)

第2章 数据类型与运算符(Data types and Operators) I think everybody in this country should ...

2555
来自专栏Play & Scala 技术分享

Scala 谜题 - 有趣的类型转换

3407
来自专栏和蔼的张星的图像处理专栏

167. 链表求和相加,并记录进位情况

你有两个用链表代表的整数,其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序,使得第一个数字位于链表的开头。写出一个函数将两个整数相加,用链表形式返回...

1604
来自专栏Java技术栈

Java父类强制转换子类原则

最近,微信群友在讨论子类父类的转换问题,其实不难,给大家用实例来说明一下就很明了了。 我们知道Java中子类转换成父类是没有任何问题的,那父类可以转换成子类吗?...

4358
来自专栏LinkedBear的个人空间

唠唠SE的面向对象-04——this关键字 原

this关键字代表是对象的引用。也就是this在指向一个对象,所指向的对象就是调用该方法的对象引用。

662
来自专栏武培轩的专栏

剑指Offer-合并两个排序的链表

题目描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 思路 思路一(迭代): 首先处理空链表,当其中一个为空链...

2584
来自专栏和蔼的张星的图像处理专栏

451. 两两交换链表中的节点链表处理

给一个链表,两两交换其中的节点,然后返回交换后的链表。 样例 给出 1->2->3->4, 你应该返回的链表是 2->1->4->3。 你的算法只能使用常...

1923
来自专栏用户2442861的专栏

JavaScript 正则表达式上——基本语法

JavaScript种正则表达式有两种定义方式,定义一个匹配类似 <%XXX%> 的字符串

661
来自专栏海天一树

小朋友学Python(20):面向对象

一、类与对象 例1 class Employee: 'Base class of employee' empCount = 0 def __i...

3329

扫码关注云+社区

领取腾讯云代金券