Start learning free

LESSON 314 OF 442 · LINKED LISTS

Linked List Cycle in Kotlin: Fast and Slow 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

    KOTLIN · LINKED LISTS

    Linked List Cycle in Kotlin, explained

    Problem overview

    The function hasCycle receives head, the first node of a singly linked list, or null for an empty list. It returns true if some node can be reached again by following next pointers, which happens when the tail's next points back to an earlier node. Otherwise it returns false.

    The value pos in the examples only describes how the test list was built, by naming the node the tail connects to. The function never receives it, so it must find the cycle from the nodes alone.

    For [3, 2, 0, -4] with the tail linked back to the node holding 2, the walk goes 3, 2, 0, -4, 2, 0, -4, 2 and so on forever, so the answer is true. For [1] with no link back, the walk ends after one node, so the answer is false.

    Approach: a slow pointer and a fast pointer

    The obvious solution remembers every node already visited, for example in a set, and reports a cycle when a node shows up twice. It works, but it needs memory proportional to the list length. The follow-up asks for constant memory, and two pointers deliver it.

    Both pointers start at the head. On each turn, slow moves one node forward and fast moves two. There are two outcomes:

    • No cycle. fast runs ahead and reaches the end of the list, where next is null. The loop stops and the answer is false.
    • A cycle. Both pointers eventually enter the cycle and keep going round it. Inside the cycle, fast gains exactly one node on slow per turn, so the gap between them shrinks by one each time. It can't jump over slow, so the gap reaches zero and they stand on the same node.

    On [3, 2, 0, -4] with the tail linked to the node holding 2, the pointers move like this, showing the values they stand on:

    turn 1: slow = 2,  fast = 0
turn 2: slow = 0,  fast = 2
turn 3: slow = -4, fast = -4   (same node: cycle found)

    Step by step

    1. Declare slow and fast with var, both starting at head. They change on every turn, so they can't be val. Their type is ListNode?, because head may be null.
    2. Loop while fast != null and fast.next != null. fast jumps two nodes, so both the node it stands on and the next one must exist. If either is null, fast has reached the end. Inside the loop Kotlin treats fast as non-null (a smart cast), so fast.next needs no ?..
    3. Move slow one node, to slow!!.next. slow is always behind fast or on the same node, so it is never null here, and !! tells the compiler so.
    4. Move fast two nodes, to fast.next!!.next. The loop condition has just checked that fast.next is not null.
    5. Compare with ===. If slow === fast, both pointers stand on the same node, so return true.
    6. After the loop, return false. The loop only ends when fast has run off the list, which a cycle makes impossible.

    The solution in Kotlin

    class Solution {
    fun hasCycle(head: ListNode?): Boolean {
        var slow = head
        var fast = head
        while (fast != null && fast.next != null) {
            slow = slow!!.next
            fast = fast.next!!.next
            if (slow === fast) return true
        }
        return false
    }
}

    The Kotlin details worth a closer look:

    • === versus ==. In Kotlin, == calls equals and compares contents, while === compares references. Two different nodes can hold the same value, so only === answers the question "is this the very same node?".
    • Smart cast and !!. After fast != null succeeds, Kotlin lets you use fast as a non-null ListNode, because it is a local var that nothing else changes in between. fast.next is a property of the node, so its type is still ListNode?, and the compiler doesn't carry the earlier check over to fast.next!!.next. The !! operator converts it to non-null and throws an exception if it were null. Here the loop condition guarantees it isn't.
    • slow and fast are nullable. They get the type ListNode? from head, so slow!!.next is needed even though slow can't be null at that point.
    • The early return. if (slow === fast) return true is a one-line if with no braces. It is fine for a single statement.

    Complexity

    Time: O(n). Without a cycle, fast reaches the end after about n / 2 turns. With a cycle, slow enters the cycle after at most n turns, and then fast closes the gap, which is smaller than the cycle's length, at one node per turn. The total stays proportional to n.

    Space: O(1). Only two references are stored, however long the list is.

    Edge cases and common mistakes

    • Empty list. With head equal to null, the loop condition fails immediately and the function returns false.
    • One node. A node whose next is null has no cycle, and the loop never runs. A single node whose next points to itself is a cycle: fast and slow both move to that node on the first turn and meet, so the result is true.
    • Checking only fast != null. On a list with an odd number of nodes, fast lands on the last node, and fast.next is null. Without the second check, fast.next!! would throw a NullPointerException.
    • Comparing before moving. Both pointers start on the same node. If you compared them at the top of the loop, you would report a cycle for every non-empty list.
    • Comparing values. In [1, 1] without a cycle, the two nodes hold equal values. Comparing values would report a cycle that isn't there.

    Testing

    • [3, 2, 0, -4], tail linked to index 1: true.
    • [1, 2], tail linked to index 0: true.
    • [1] with no link: false.
    • [1] linked to itself: true.
    • [1, 2, 3, 4, 5] with no link: false.
    • An empty list: false.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free