Linked List Cycle

栏目: IT技术 · 发布时间: 5年前

内容简介:时间复杂度: O(n), 空间复杂度: O(1)这是一道经典的链表题目 - 环形链表,基本的解题思路是双指针技巧里面的快慢指针。这两个指针的适当速度应该是多少?

时间复杂度: O(n), 空间复杂度: O(1)

解题思路

这是一道经典的链表题目 - 环形链表,基本的解题思路是双指针技巧里面的快慢指针。

  • 如果没有环,快指针将停在链表的末尾。
  • 如果有环,快指针最终将与慢指针相遇。

这两个指针的适当速度应该是多少?

一个安全的选择是每次移动慢指针一步,而移动快指针两步。每一次迭代,快速指针将额外移动一步。如果环的长度为 M,经过 M 次迭代后,快指针肯定会多绕环一周,并赶上慢指针。

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        if head == nil || head?.next == nil {
            return false
        }
        var slow = head
        var fast = head?.next
        
        while fast?.next != nil && fast?.next?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
            if slow === fast {
                return true
            }
        }
        return false
    }
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

App研发录:架构设计、Crash分析和竞品技术分析

App研发录:架构设计、Crash分析和竞品技术分析

包建强 / 机械工业出版社 / 2015-10-21 / CNY 59.00

本书是作者多年App开发的经验总结,从App架构的角度,重点总结了Android应用开发中常见的实用技巧和疑难问题解决方法,为打造高质量App提供有价值的实践指导,迅速提升应用开发能力和解决疑难问题的能力。本书涉及的问题有:Android基础建设、网络底层框架设计、缓存、网络流量优化、制定编程规范、模块化拆分、Crash异常的捕获与分析、持续集成、代码混淆、App竞品技术分析、项目管理和团队建设等......一起来看看 《App研发录:架构设计、Crash分析和竞品技术分析》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

MD5 加密
MD5 加密

MD5 加密工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具