Find Middle of Linked List
Find the middle node of a singly linked list in a single pass using the slow and fast pointer technique (Floyd's algorithm variation). When the fast pointer reaches the end, the slow pointer is at the middle. For even-length lists, returns the second middle node. This O(n) time, O(1) space solution is fundamental for many linked list problems including palindrome checking and merge sort.
Visualization
Interactive visualization for Find Middle of Linked List
Interactive visualization with step-by-step execution
Implementation
1function middleNode(head: ListNode | null): ListNode | null {
2 let slow = head;
3 let fast = head;
4
5 while (fast && fast.next) {
6 slow = slow!.next;
7 fast = fast.next.next;
8 }
9
10 return slow;
11}Deep Dive
Theoretical Foundation
Finding the middle without knowing the length requires the two-pointer technique. Initialize slow and fast pointers at head. Move slow by 1 step and fast by 2 steps in each iteration. When fast reaches the end (null or last node), slow is at the middle. For odd length n, slow points to the exact middle. For even length n, slow points to the second middle (n/2 + 1). This works because fast moves twice as fast, so when it covers n nodes, slow covers n/2. Time: O(n) single pass. Space: O(1).
Complexity
Time
O(n)
O(n)
O(n)
Space
O(1)
Applications
Industry Use
Palindrome checking (split at middle)
Merge sort on linked lists (divide step)
Binary search on linked lists
Finding center element in sequences
List splitting operations
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.