Start learning free

LESSON 315 OF 443 · LINKED LISTS

Linked List Cycle in Swift: Floyd's Slow and Fast Pointers

Practice O(n) Read the full explanation

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. In the examples, pos is the index of the node that the tail's next pointer is connected to (-1 means no cycle). pos only describes how the example list is built: the tests build the cycle themselves, and pos is not passed to your function, which receives only head.

Return true if there is a cycle in the linked list. Otherwise, return false.

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed):
3 -> 2 -> 0 -> -4, and -4's next is the node 2 again.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node:
1 -> 2, and 2's next is the node 1 again.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

 

Constraints:

  • The number of the nodes in the list is in the range [0, 104].
  • -105 <= Node.val <= 105
  • pos is -1 or a valid index in the linked-list.

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?

STEP 1 OF 6
    Ctrl + Enter to check

    SWIFT · LINKED LISTS

    Linked List Cycle in Swift, explained

    Problem overview

    The method hasCycle receives head, the first node of a singly linked list (a ListNode?, which is nil for an empty list). It returns true if following the next pointers can bring you back to a node you have already visited, and false if the walk reaches the end of the list.

    In the first example the list is [3, 2, 0, -4] and the tail points back to the node at index 1, so the answer is true. In the second, [1, 2], the tail points back to the head: true. A single node whose next is nil has no cycle: false. The cycle position is only used to build the test lists; the method never sees it.

    The follow-up asks for constant extra memory, and that is what this lesson solves.

    Approach: two pointers at different speeds

    The obvious solution records every node you visit in a set and reports a cycle when a node shows up twice. It works, but it needs memory proportional to the length of the list.

    The constant-memory idea uses two pointers that start on the head. slow moves one node per turn and fast moves two. Two things can happen:

    • There is no cycle. fast runs off the end of the list long before slow does, and the loop stops.
    • There is a cycle. Both pointers eventually enter it. Inside the cycle, fast gains exactly one node on slow every turn, so the gap between them shrinks by one each time. A gap that shrinks by one can't skip over zero, so the two pointers land on the same node.

    With [3, 2, 0, -4] and the tail joined to index 1, the pointers visit these positions: after turn 1, slow is on index 1 and fast on index 2; after turn 2, slow is on 2 and fast on index 1 (it went 2, 3, then back to 1); after turn 3, both are on index 3. They meet, so the method returns true.

    Step by step

    1. Declare slow and fast with var, both starting at head. They change on every turn, and both have the optional type ListNode? because they can become nil.
    2. Loop while fast can move two nodes. That needs the node it stands on, and the one after it, to exist. The condition fast != nil && fast!.next != nil checks both. The force unwrap in the second half is safe because && stops at the first false and never evaluates fast! when fast is nil.
    3. Advance slow by one. It trails fast, so it is never nil at this point.
    4. Advance fast by two with fast!.next!.next. The loop condition already guaranteed the first next exists. The result may be nil, which ends the loop on the next check.
    5. Compare the pointers with ===. If they are the same object, the walk has gone round a cycle, so return true.
    6. Return false after the loop. The loop only ends when fast has fallen off the list, which can't happen inside a cycle.

    The solution in Swift

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

    Swift details worth knowing:

    • ===, not ==. ListNode is a class, and the triple-equals operator asks whether two references point to the same object. Two different nodes holding the same value are not equal under ===, which is exactly what the problem needs: a list like [1, 1, 1] without a cycle must not be reported as cyclic. A plain == on two class instances that don't conform to Equatable doesn't compile: the compiler reports binary operator '==' cannot be applied to two 'ListNode' operands.
    • Comparing optionals. slow === fast works on ListNode? values, so it is also fine when both are nil. In the code above that can't happen, because slow was just moved onto a real node.
    • Force unwraps. Each ! follows a check that guarantees a value. An unwrap of nil would crash the program, so the order of the loop condition matters: swapping its two parts would unwrap fast before testing it.
    • Assignment, not copying. Assigning a node to slow copies the reference only. Nothing in the list changes.

    Complexity

    Time: O(n). Without a cycle, fast reaches the end after about n / 2 turns. With a cycle, slow needs at most n turns to reach the cycle, and then the gap closes by one per turn, which takes at most the length of the cycle. Both parts are bounded by the list size.

    Space: O(1). The method keeps two references and nothing that grows with the input.

    Edge cases and common mistakes

    • Empty list. With head = nil, the condition fails at once and the method returns false.
    • One node. If its next is nil the answer is false. If the node points to itself, one turn puts both pointers on it and the answer is true.
    • Checking only fast != nil. Then fast!.next!.next crashes on a list with an odd number of nodes, because fast!.next is nil when fast stands on the last node.
    • Comparing values. slow!.val == fast!.val reports a cycle in [1, 1] when there is none. Compare nodes, not values.
    • Comparing before moving. Both pointers start on head, so a test before the first move would always succeed. The comparison belongs after the pointers move.

    Testing

    • [3, 2, 0, -4] with the tail joined to index 1 gives true.
    • [1, 2] with the tail joined to index 0 gives true.
    • [1] with no cycle gives false, and [1] pointing to itself gives true.
    • [1, 2, 3, 4, 5] with no cycle gives false, and an empty list gives false.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free