iOS Interview - Leetcode 141. Linked List Cycle

May 14, 20242 min read#swift, #interview, #leetcode

Leetcode: 141. Linked List Cycle

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

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

Quick Drop logo

Profile picture

Personal blog by An Tran. I'm focusing on creating useful apps.
#Swift #Kotlin #Mobile #MachineLearning #Minimalist


© An Tran - 2024