Find Middle of Linked List Visualizer - Fast & Slow Pointers

Singly Linked List: how it works

A Singly Linked List is a linear data structure of nodes where each node contains a data field and a pointer to the next node.

1. Node Structure

   Each node holds a value and a "next" pointer to the following node. The last node points to null.

2. Search

   Traverse the list from the Head, comparing each node until the target value is found or null is reached.

3. Append (Insert at Tail)

   Creates a new node and links the current Tail to this new node, making it the new Tail.

4. Prepend (Insert at Head)

   Creates a new node and makes it the new Head, linking it to the previous head.

5. Reverse Linked List

   Inverts the direction of all pointers in the list. The head becomes the tail and the tail becomes the head.

6. Remove N-th from End

   Uses two pointers separated by N nodes. When the leading pointer reaches the end, the trailing pointer is at the node before the one to remove.

7. Find Middle (Fast & Slow Pointers)

   The "Slow" pointer moves 1 step while the "Fast" pointer moves 2 steps. When Fast reaches the end, Slow is at the exact middle.

Complexity

Best-case time

O(1)

Average time

O(N)

Worst-case time

O(N)

Space

O(N)

Insertion at Head (Prepend) is O(1). Search and general deletion takes O(N) time because we lack random access to elements.