iOS Interview - Leetcode 141. Linked List Cycle

May 14, 2024 • 2 min read • #swift, #interview, #leetcode

Primary idea: Floyd’s Cycle Finding Algorithm: 2 pointers, slow and fast. slow pointer advances one step at a time, fast pointer advances 2 steps at a time. Check if fast pointer meets slow point at some point.
Time Complexity: O(n)
Space Complexity: O(1)

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

    public func print() {
        var node: ListNode? = self
        var result = ""
        while node != nil {
            result += "\(node!.val)"
            node = node?.next
            if node != nil {
                result += " -> "
            }
        }
        Swift.print(result)
    }
}

func hasCycle(_ head: ListNode?) -> Bool {
    var slow = head
    var fast = head?.next

    while slow != nil, fast != nil {
        guard slow !== fast else { return true }

        slow = slow?.next
        fast = fast?.next?.next
    }

    return false
}

let head1 = ListNode(3)
let cycleNode1 = ListNode(2)
head1.next = cycleNode1
head1.next?.next = ListNode(0)
head1.next?.next?.next = ListNode(-4)
head1.next?.next?.next?.next = cycleNode1
print(hasCycle(head1)) // true

let head2 = ListNode(1)
head2.next = ListNode(2)
head2.next?.next = head2
print(hasCycle(head2)) // true

let head3 = ListNode(1)
print(hasCycle(head3)) // false

Further reading