DSA problem
Delete the Middle Node of a Linked List
You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.
The middle node of a list of size n is the node at the 0-indexed position floor(n / 2), where floor rounds down to the nearest integer. For a list of length 7 the middle is index 3; for a list of length 4 the middle is index 2. If the list has only one node, deleting the middle leaves an empty list, so you must return null.
A two-pass solution first counts the nodes, then walks again to the node before the middle and unlinks it. That works but touches the list twice. The cleaner approach finds the middle in a single traversal.
The optimal technique uses the fast and slow pointer idiom. A fast pointer moves two steps per iteration while a slow pointer moves one; when fast reaches the end, slow sits on the middle. By starting fast one node ahead (or advancing it by two before slow begins), you can instead land slow on the node just before the middle, enabling a direct O(1) splice. The whole job finishes in one pass with O(1) extra space.
Examples
head = [1,3,4,7,1,2,6][1,3,4,1,2,6]head = [1,2,3,4][1,2,4]head = [2,1][2]Constraints
- The number of nodes in the list is in the range [1, 10^5].
- 1 <= Node.val <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.