LeetCode Entry

141. Linked List Cycle

4.09.2023 easy 2023 kotlin

Detect a cycle in a LinkedList

141. Linked List Cycle easy blog post substack

image.png

Problem TLDR

Detect a cycle in a LinkedList

Intuition

Use tortoise and rabbit technique

Approach

Move one pointer one step at a time, another two steps at a time. If there is a cycle, they will meet.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(log(n))\) for recursion (iterative version is O(1))

Code


    fun hasCycle(slow: ListNode?, fast: ListNode? = slow?.next): Boolean =
      fast != null && (slow == fast || hasCycle(slow?.next, fast?.next?.next))