Start learning free

LESSON 314 OF 442 · LINKED LISTS

Linked List Cycle in Scala: 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

    SCALA · LINKED LISTS

    Linked List Cycle in Scala, explained

    Problem overview

    The method hasCycle receives head, the first ListNode of a singly linked list, and returns a Boolean: true if following the next pointers can bring you back to a node you have already visited, false if the chain ends. A list can be empty, in which case head is null.

    In the first example the list is 3 -> 2 -> 0 -> -4 and the tail's next points back to the node holding 2. Walking forward never ends, so the answer is true. In the second example 1 -> 2 has a tail that points back to the head, again true. In the third, a single node 1 whose next is null, the walk stops after one step, so the answer is false. The index pos in the statement only describes how the test list was built. The method never receives it.

    Approach: two pointers at different speeds

    The obvious idea is to remember every node you visit and return true when you see one a second time. That works in linear time but needs a set that grows with the list. The follow-up asks for constant memory.

    The constant-memory idea is Floyd's tortoise and hare. Start two pointers at head. Move slow one node per turn and fast two nodes per turn.

    • If the list has no cycle, fast reaches the end, where next is null, and the loop stops. The answer is false.
    • If the list has a cycle, both pointers eventually enter it and keep going around. Inside the cycle, each turn fast gains exactly one node on slow, so the gap between them shrinks by one per turn. A gap that shrinks by one each time reaches zero, and zero means they stand on the same node. They can't jump over each other, because a gap of 1 becomes 0, not -1.

    Only two references are stored, so the extra space is constant.

    Step by step

    1. Declare slow and fast with var, both starting at head. They are reassigned on every turn, so val would not do.
    2. Loop while fast != null and fast.next != null. Fast jumps two nodes, so the node it stands on and the one after it must both exist. The order of the two tests matters: && stops at the first false, so fast.next is only read when fast is not null.
    3. Move slow one node with slow = slow.next.
    4. Move fast two nodes with fast = fast.next.next. This is safe because the loop condition just checked both links.
    5. Compare the pointers with eq. If slow eq fast, they are on the same node, so a cycle exists and the method returns true. The comparison happens after both pointers moved. At the start they are equal, since both are head, and checking before moving would report a cycle in every non-empty list.
    6. Finish with false. If the loop ends, fast fell off the end of the list, so there is no cycle. The last expression of a Scala method is its result, so no return is needed here.

    The solution in Scala

    class Solution {
    def 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 eq fast) return true
        }
        false
    }
}

    The Scala details worth knowing:

    • eq is reference identity. It asks whether both sides are the very same object. That is the question here: two different nodes may hold equal values, and they are still different nodes. For a plain class like ListNode, == would also end up comparing references, but eq states the intent and keeps working if a class ever defines its own equals.
    • return inside a loop. Normally the last expression is the value of a method, but a value in the middle of a loop can only be sent out with return. Here return true leaves the method at once, and the final false is the value only if the loop ends on its own.
    • null is allowed for ListNode. The lesson's nodes use null to mean "no next node", so the checks fast != null and fast.next != null are ordinary comparisons.
    • Method as an expression. The if without an else is used as a statement, so its value is discarded. That is fine because the branch exits through return.

    Complexity

    Time: O(n). Without a cycle, fast covers the list in about n / 2 turns. With a cycle, slow enters the cycle after at most n turns, and from then on the gap between the pointers is smaller than the cycle's length and shrinks by one per turn, so they meet within another n turns or fewer.

    Space: O(1). The method keeps two references, whatever the length of the list.

    Edge cases and common mistakes

    • Empty list. With head = null, the loop condition fails immediately and the method returns false.
    • One node. A node whose next is null has no cycle. A node whose next is itself is a cycle of length 1: fast and slow both move to that node on the first turn, so they meet and the method returns true.
    • Equal values are not a cycle. A list 1 -> 1 -> 1 -> 1 with no loop back returns false. Comparing values (slow.`val` == fast.`val`) would answer true wrongly. Compare the nodes themselves.
    • Testing for equality before moving. Both pointers start on head, so the check must come after the moves.
    • Reading fast.next.next without checking fast.next. In a list with an odd number of nodes, fast lands on the last node, and its next is null. Reading .next of null would throw a NullPointerException.
    • Moving fast by one node. If both pointers move at the same speed, the gap never changes and they never meet.

    Testing

    • [3, 2, 0, -4] with the tail linked to the second node gives true.
    • [1, 2, 3] with no link back gives false.
    • [1] with its next pointing to itself gives true.
    • [1, 1, 1, 1] with no link back gives false.
    • An empty list (null) gives false.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free