Linked List Cycle in Swift — Floyd's Tortoise & Hare & More

Linked List Cycle (#141 — Easy): Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node can be reached again by continuously following the next pointer.

Problem Statement

Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node can be reached again by continuously following the next pointer.

Example:

Input: head = [3,2,0,-4], pos = 1 (tail connects to node index 1)
Output: true

Approach: Floyd’s Tortoise & Hare (Optimal)

Time: O(n) | Space: O(1)

Two pointers at different speeds: fast moves 2 steps, slow moves 1. If there’s a cycle, fast will eventually lap slow and they’ll meet. O(1) space.

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

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

Approach: Hash Set

Time: O(n) | Space: O(n)

Store every visited node in a set. If we revisit a node, a cycle exists. Uses O(n) space but works even when you cannot modify the list.

func hasCycleSet(_ head: ListNode?) -> Bool {
    var seen = Set<ObjectIdentifier>()
    var node = head
    while let n = node {
        let id = ObjectIdentifier(n)
        if seen.contains(id) { return true }
        seen.insert(id)
        node = n.next
    }
    return false
}

Key Takeaways

• Start with the brute-force approach to understand the problem
• Floyd’s Tortoise & Hare (Optimal) gives the optimal O(n) solution
• Practice this pattern — it appears frequently in coding interviews

Related Problems

• Linked List Cycle in Python
• Linked List Cycle in Dart
• Linked List Cycle in Go
• Remove Duplicates from Sorted Array in Swift
• Reverse Linked List in Swift
• Reverse String in Swift

FAQ

What is the best approach to solve Linked List Cycle in Swift?

The recommended approach is Floyd’s Tortoise & Hare (Optimal), which runs in O(n) time with O(1) space. The full Swift implementation is shown above.

What is the time complexity of Linked List Cycle in Swift?

Using Floyd’s Tortoise & Hare (Optimal), the time complexity is O(n) and the space complexity is O(1).

Happy coding!