Skip to content
Hello Python

Trace Fast and Slow Pointers

Practice ExerciseInterviewEasyFast and Slow Pointers

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement middle_link_index(next_indices, head). next_indices stores an acyclic singly linked chain using -1 as null. Return the middle node index reached by advancing slow one link and fast two links; for an even-length chain return the second middle. Return -1 for an empty head.

Starter code

def middle_link_index(next_indices, head):
    pass
Test cases

odd-chain

{
  "args": [
    [
      1,
      2,
      3,
      4,
      -1
    ],
    0
  ]
}

Expected: 2

even-chain

{
  "args": [
    [
      1,
      2,
      3,
      -1
    ],
    0
  ]
}

Expected: 2

Wizard outline
  1. Step 1: Preserve the empty-head sentinel

    Return -1 before indexing next_indices when the chain has no head. The sentinel boundary must be safe before either pointer reads a link.

  2. Step 2: Advance through an odd chain

    Move slow one edge and fast two edges until fast reaches the final node. An odd-length chain demonstrates the two-to-one speed invariant without the second-middle boundary.

  3. Step 3: Return the second middle for even chains

    Continue while fast has one next edge so slow advances to the required second middle. The final boundary distinguishes the product contract from variants that return the first middle.

Footguns and prerequisites
  • Stopping when fast itself is null but not checking fast.next can index -1 as a valid Python list position.
  • Changing the loop boundary to stop one iteration earlier returns the first middle instead of the required second middle.
  • linked lists
Reviewed references
Prepared Interview Problems
  • Find a Linked-List Cycle Entrance(opens in a new tab)

    Trace Fast and Slow Pointers isolates after each loop, slow has advanced one link for every two links attempted by fast. That focused state discipline is required when implementing linked cycle entry index as a complete Interview Problem.

  • Find the Duplicate Number(opens in a new tab)

    Trace Fast and Slow Pointers isolates after each loop, slow has advanced one link for every two links attempted by fast. That focused state discipline is required when implementing find duplicate number as a complete Interview Problem.

  • Remove Nth Node From End(opens in a new tab)

    Trace Fast and Slow Pointers isolates after each loop, slow has advanced one link for every two links attempted by fast. That focused state discipline is required when implementing remove nth node from end as a complete Interview Problem.

  • Reorder List(opens in a new tab)

    Trace Fast and Slow Pointers isolates after each loop, slow has advanced one link for every two links attempted by fast. That focused state discipline is required when implementing reorder list as a complete Interview Problem.

  • Sorted List to Balanced BST(opens in a new tab)

    Trace Fast and Slow Pointers isolates after each loop, slow has advanced one link for every two links attempted by fast. That focused state discipline is required when implementing sorted list to bst as a complete Interview Problem.

Recommended approach and implementation

A runner moving twice as fast reaches the end when a one-step runner reaches the midpoint, without counting length first. After each loop, slow has advanced one link for every two links attempted by fast.

Why it works: Fast reaches the end after twice as many link advances as slow, placing slow at the midpoint boundary. The explicit null checks stop before an invalid dereference and distinguish odd from even lengths correctly.

def middle_link_index(next_indices, head):
    slow = fast = head
    while fast != -1 and next_indices[fast] != -1:
        slow = next_indices[slow]
        fast = next_indices[next_indices[fast]]
    return slow