Floyd’s Cycle Detection Algorithm In Swift

Or how I forgot === in Swift

I’m not perfect my any means. I’ve just proven it with my latest attempt at a LeetCode problem.

Given the head of a linked list, determine if the linked list contains a cycle.

If you can see from the (too small, sorry) image above there is a cycle in that linked list

0 →1 →2 →1 →2…ad infinitum

So this challenge is about finding out if there is a cycle in any given linked list.

What could go wrong?

Clue in the question?

Is this a clickbait subheading? Because the only clue in the question is that you are given a simple implementation of a linked list. That is, indeed, it. Or rather, here it is:

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

Here the initializer doesn’t take in a parameter for the next node, so that property would need to be set directly. Other than that? There isn’t too much to see here that isn’t in my initial

Simple answers

Probably only simple people give simple answers. Using an array is a simplistic solution.

func hasCycle(_ head: ListNode?) -> Bool {
    var nodeArray: [ListNode] = []
    var current = head
    while current != nil {
        if nodeArray.contains(current!) {
            return true
        }
        nodeArray.append(current!)
        current = current?.next
    }
    return false
}

Unfortunately for LeetCode this is just too slow. Of course, potential commenter, there is also a poor habit of force-unwrap but for LeetCode problems I’m focusing on the algorithm here.

So although append is an O(1) operation in Swift, contains is an O(n) operation.

It just won’t get through!

Simple answers vol II

Let us get rid of that O(n) operation. contains for a Set has complexity of O(1) which is clearly an improvement.

This is where I’m going to come unstuck!

class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        var nodeSet: Set<ListNode> = []
        var current = head
        while current != nil {…