Logo

Kode$word

LeetCode 2095. Delete the Middle Node of a Linked List – Fast and Slow Pointer Approach
LeetCode 2095. Delete the Middle Node of a Linked List – Fast and Slow Pointer Approach

LeetCode 2095. Delete the Middle Node of a Linked List – Fast and Slow Pointer Approach

A Complete Guide with Intuition, Detailed Dry Run, and Optimal Solution in O(n) Time

13 views
0
0
LeetCodeMediumLinked ListFast and Slow Pointer
Github icon

🔗 Try This Problem

https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/

🎥 Video Explanation


Problem Explanation

You are given the head of a singly linked list. The task is to remove the middle node and return the updated list.

The middle node is defined using 0-based indexing:

Middle Index = ⌊n / 2⌋

Where n is the total number of nodes.

Example

Input: [1, 3, 4, 7, 1, 2, 6]
Index: 0 1 2 3 4 5 6
  1. n = 7
  2. Middle index = 3
  3. Node to remove = 7
Output: [1, 3, 4, 1, 2, 6]

Approach 1: Brute Force (Two Traversals)

Idea

  1. Traverse the list to count total nodes
  2. Compute middle index
  3. Traverse again to delete that node

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Limitation

This approach requires two passes, which is not optimal when a single traversal solution exists.

Approach 2: Fast and Slow Pointer (Optimal)

Intuition

Use two pointers:

  1. Slow pointer moves one step at a time
  2. Fast pointer moves two steps at a time

When the fast pointer reaches the end of the list:

Slow pointer will be at the middle node

Important Detail

To remove the middle node, access to the previous node is required.

Therefore, maintain an additional pointer:

prev → tracks node before slow

Algorithm Steps

  1. Initialize:
  2. slow = head
  3. fast = head
  4. prev = null
  5. Traverse:
  6. Move fast by 2 steps
  7. Move slow by 1 step
  8. Update prev = slow (before moving slow)
  9. When loop ends:
  10. slow points to middle node
  11. prev points to node before middle
  12. Delete node:
prev.next = slow.next

Detailed Dry Run

Input

1 → 3 → 4 → 7 → 1 → 2 → 6

Initial State

slow = 1
fast = 1
prev = null

Iteration 1

fast → 4
slow → 3
prev → 1

Iteration 2

fast → 1
slow → 4
prev → 3

Iteration 3

fast → null
slow → 7
prev → 4

After Loop

slow = 7 (middle node)
prev = 4

Deletion

prev.next = slow.next

Result:

1 → 3 → 4 → 1 → 2 → 6

Optimized Code (Java)

class Solution {
public ListNode deleteMiddle(ListNode head) {

// Edge case: single node
if(head == null) return head;
if(head.next == null) return null;

ListNode slow = head;
ListNode fast = head;
ListNode prev = null;

// Traverse using fast and slow pointer
while(fast != null && fast.next != null){
fast = fast.next.next;
prev = slow;
slow = slow.next;
}

// Remove middle node
prev.next = slow.next;

return head;
}
}

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)
  1. Only one traversal of the linked list
  2. No extra data structures used

Edge Cases

Single Node

Input: [1]
Output: []

Two Nodes

Input: [2, 1]
Output: [2]

Even Length List

Input: [1, 2, 3, 4]
  1. n = 4
  2. Middle index = 2
  3. Node removed = 3

Key Takeaways

  1. Fast and slow pointer reduces two-pass solution to one-pass
  2. Tracking the previous node is necessary for deletion
  3. Works efficiently for large linked lists
  4. A fundamental pattern used in multiple linked list problems

Conclusion

The fast and slow pointer technique provides an elegant and efficient way to identify and remove the middle node in a linked list. By leveraging different traversal speeds, the problem can be solved in a single pass with constant space, making it optimal for both interviews and practical implementations.

Related Articles

LeetCode 203: Remove Linked List Elements – Step-by-Step Guide for Beginners

LeetCode 203: Remove Linked List Elements – Step-by-Step Guide for Beginners

Learn How to Remove Nodes from a Linked List Using Iteration, Edge Case Handling, and Dummy Node Technique (With Clear Intuition)

Read Article
Remove Nth Node From End – The Smart Way to Solve in One Pass (LeetCode 19)

Remove Nth Node From End – The Smart Way to Solve in One Pass (LeetCode 19)

Stop Counting Twice! Learn the Two-Pointer Trick to Remove Nodes Efficiently from the End of a Linked List

Read Article
LeetCode 328: Odd Even Linked List – Clean and Easy Explanation with Multiple Approaches

LeetCode 328: Odd Even Linked List – Clean and Easy Explanation with Multiple Approaches

Learn How to Rearrange a Linked List by Odd and Even Positions Using Optimal O(1) Space Approach

Read Article
Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Learn how to find the peak index in a mountain array using multiple approaches including brute force, linear scan, and an optimized binary search solution with O(log n) time complexity.

Read Article

Ai Assistant Kas