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
    }
}

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

查看所有标签

猜你喜欢:

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

Persuasive Technology

Persuasive Technology

B.J. Fogg / Morgan Kaufmann / 2002-12 / USD 39.95

Can computers change what you think and do? Can they motivate you to stop smoking, persuade you to buy insurance, or convince you to join the Army? "Yes, they can," says Dr. B.J. Fogg, directo......一起来看看 《Persuasive Technology》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试