The Two-Speed Template in Python, Java and TypeScript

One loop that moves slow by one and fast by two, with the stop condition and the check after each move marked.

The two-speed template is one loop that moves slow by one node and fast by two, while fast and fast.next both exist. Two things change between problems, and they are highlighted: the loop condition, and the check after the moves, which is nothing when the answer is the middle and slow is fast when it is a cycle. Each listing builds 10 20 30 40 50 60, finds its middle, then checks it for a cycle without and with a link from 60 back to 30.

The two-speed template in three languages

fast_and_slow.pypy

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None


def build(values, cycle_start=None):
    nodes = [ListNode(val) for val in values]
    for node, following in zip(nodes, nodes[1:]):
        node.next = following
    if cycle_start is not None:
        nodes[-1].next = nodes[cycle_start]
    return nodes[0]


def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


values = [10, 20, 30, 40, 50, 60]
print("middle:", middle(build(values)).val)
print("cycle without a back link:", has_cycle(build(values)))
print("cycle with 60 linking to 30:", has_cycle(build(values, 2)))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

middle: 40
cycle without a back link: False
cycle with 60 linking to 30: True

FastAndSlow.javajava

public class FastAndSlow {
    static class ListNode {
        final int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    static ListNode build(int[] values, int cycleStart) {
        ListNode[] nodes = new ListNode[values.length];
        for (int i = 0; i < values.length; i++) {
            nodes[i] = new ListNode(values[i]);
        }
        for (int i = 0; i + 1 < values.length; i++) {
            nodes[i].next = nodes[i + 1];
        }
        if (cycleStart >= 0) {
            nodes[values.length - 1].next = nodes[cycleStart];
        }
        return nodes[0];
    }

    static ListNode middle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    static boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] values = {10, 20, 30, 40, 50, 60};
        System.out.println("middle: " + middle(build(values, -1)).val);
        System.out.println("cycle without a back link: " + hasCycle(build(values, -1)));
        System.out.println("cycle with 60 linking to 30: " + hasCycle(build(values, 2)));
    }
}

OutputRan with eclipse-temurin:25.0.4.1_1-jdk-noble (Java 25.0.4.1)

middle: 40
cycle without a back link: false
cycle with 60 linking to 30: true

fast_and_slow.tsts

class ListNode {
  next: ListNode | null = null;

  readonly val: number;

  constructor(val: number) {
    this.val = val;
  }
}

function build(values: number[], cycleStart: number | null = null): ListNode {
  const nodes = values.map((val) => new ListNode(val));
  for (let i = 0; i + 1 < nodes.length; i++) {
    nodes[i].next = nodes[i + 1];
  }
  if (cycleStart !== null) {
    nodes[nodes.length - 1].next = nodes[cycleStart];
  }
  return nodes[0];
}

function middle(head: ListNode): ListNode {
  let slow: ListNode = head;
  let fast: ListNode | null = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next!;
    fast = fast.next.next;
  }
  return slow;
}

function hasCycle(head: ListNode): boolean {
  let slow: ListNode = head;
  let fast: ListNode | null = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next!;
    fast = fast.next.next;
    if (slow === fast) {
      return true;
    }
  }
  return false;
}

const values = [10, 20, 30, 40, 50, 60];
console.log("middle:", middle(build(values)).val);
console.log("cycle without a back link:", hasCycle(build(values)));
console.log("cycle with 60 linking to 30:", hasCycle(build(values, 2)));

OutputRan with node:24.22.0-trixie-slim (Node 24.22.0), TypeScript 5.9.3

middle: 40
cycle without a back link: false
cycle with 60 linking to 30: true

All three print the middle 40, no cycle on the plain list and a cycle once 60 links back to 30. The cycle check compares nodes by identity, is in Python, == on references in Java and === in TypeScript, never by value: two different nodes can hold the same value, and only reaching the same node proves a loop. The loop condition checks fast before fast.next, so a list of one node, or an empty fast, stops the loop instead of failing on a missing node. The class is named ListNode in all three because TypeScript's standard library already declares a global Node type for web pages. Both functions are O(n) time and O(1) extra space for n nodes.

← → move through sections and cards