Delete the Middle Node of a Linked List solution and explanation
Google
TCS
9 more videos on this problem
Delete the Middle Node of a Linked List | Flipkart | Amazon | Microsoft | Leetcode 2095codestorywithMIK · 14:36 · 17K views
Delete the Middle Node of a Linked List - LeetCode 2095 - Python #leetcode #leetcode75 #pointersDeepti Talesra · 6:05 · 4K views
2095. Delete the Middle Node of a Linked List || Java || Leetcode || HindiCoding Sphere · 4:57 · 3K views
Leetcode | 2095. Delete the Middle Node of a Linked List | Medium | Java SolutionDeveloper Docs · 6:48 · 1K views
Solving the 'Delete the Middle Node of a Linked List' Problem in Java LeetCode 75 Study PlanCoding with Christian · 8:17 · 377 views
2095. Delete the Middle Node of a Linked List | Leetcode Daily - PythonLeetcode Daily · 5:45 · 282 views
2095. Delete the Middle Node of a Linked List || Python || LeetCodeThe Local Coder! · 5:49 · 268 views
Delete the Middle Node of a Linked List | Leetcode 2095 | Python | Explained | Simple | 2 SolutionRubenOrtega · 9:08 · 239 views
Delete the Middle Node of a Linked List | LeetCode 2095 - Pythonimpoldev · 4:11 · 172 views
Leetcode 2095. Delete the Middle Node of a Linked List - basic practice of slow-fast-pointers methodCode-Yao · 8:57 · 164 views
The problem
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 linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.
- For
n=1,2,3,4, and5, the middle nodes are0,1,1,2, and2, respectively.
Example 1:
Input: head = [1,3,4,7,1,2,6] Output: [1,3,4,1,2,6] Explanation: The above figure represents the given linked list. The indices of the nodes are written below. Since n = 7, node 3 with value 7 is the middle node, which is marked in red. We return the new list after removing this node.
Example 2:
Input: head = [1,2,3,4] Output: [1,2,4] Explanation: The above figure represents the given linked list. For n = 4, node 2 with value 3 is the middle node, which is marked in red.
Example 3:
Input: head = [2,1] Output: [2] Explanation: The above figure represents the given linked list. For n = 2, node 1 with value 1 is the middle node, which is marked in red. Node 0 with value 2 is the only node remaining after removing node 1.
Constraints:
- The number of nodes in the list is in the range
[1, 105]. 1 <= Node.val <= 105
Approach overview
Problem Overview: You receive the head of a singly linked list and must delete the middle node, returning the updated list. The middle is defined as the ⌊n / 2⌋ index (0‑based). If the list has only one node, deleting the middle results in an empty list.
This problem tests your ability to traverse a linked list efficiently and manipulate node pointers without extra memory. The challenge is identifying the middle node and updating the previous node’s next pointer correctly.
Approach 1: Two-Pass Method (O(n) time, O(1) space)
Traverse the linked list once to compute its length. The middle index is n // 2. Perform a second traversal to reach the node just before the middle. Update its next pointer to skip the middle node (prev.next = prev.next.next). This approach is straightforward because you explicitly know the target index before deletion. The downside is two full passes over the list, but the complexity still remains linear with constant extra memory.
The main operations are simple pointer iteration and index tracking. If the list length is 1, return null. Otherwise, stop at index (n // 2) - 1 and rewire the pointer. This method is easy to reason about and useful when interviewers want to see a clear baseline solution for linked list traversal.
Approach 2: Two-Pointer Method (O(n) time, O(1) space)
This is the optimal one-pass technique using the classic two pointers pattern. Maintain two pointers: slow and fast. Move fast two steps at a time and slow one step. When fast reaches the end of the list, slow will be at the middle node.
To delete the middle node, you also track the previous node of slow. Each iteration updates prev = slow, then advances the pointers (slow = slow.next, fast = fast.next.next). Once the loop ends, remove the middle by setting prev.next = slow.next. This eliminates the middle node without needing the list length.
The key insight is that the fast pointer moves twice as quickly, so when it finishes the list traversal, the slow pointer has covered exactly half the distance. This technique frequently appears in linked list tasks like cycle detection, finding the middle node, and splitting lists.
Recommended for interviews: Start by explaining the two-pass counting approach to demonstrate basic linked list traversal. Then move to the one-pass two-pointer technique, which most interviewers expect. Both run in O(n) time with O(1) space, but the single-pass solution shows stronger pointer manipulation skills.
Approach 1: Approach 1: Two-Pass Method
This approach involves traversing the list twice. In the first pass, you count the number of nodes to determine the middle node's index. In the second pass, you reach the middle node and update the links to skip it.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def deleteMiddle(self, head: ListNode) -> ListNode:
if not head or not head.next:
return None
count = 0
temp = head
while temp:
count += 1
temp = temp.next
mid = count // 2
temp = head
prev = None
while mid > 0:
prev = temp
temp = temp.next
mid -= 1
if prev:
prev.next = temp.next
return headclass ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
public ListNode deleteMiddle(ListNode head) {
if (head == null || head.next == null) return null;
int count = 0;
ListNode temp = head;
while (temp != null) {
count++;
temp = temp.next;
}
int mid = count / 2;
ListNode prev = null;
temp = head;
while (mid-- > 0) {
prev = temp;
temp = temp.next;
}
if (prev != null) {
prev.next = prev.next.next;
}
return head;
}
}#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* deleteMiddle(ListNode* head) {
if (!head || !head->next) return nullptr;
ListNode* temp = head;
int count = 0;
while (temp) {
count++;
temp = temp->next;
}
int mid = count / 2;
ListNode* prev = nullptr;
temp = head;
while (mid-- > 0) {
prev = temp;
temp = temp->next;
}
if (prev) {
prev->next = prev->next->next;
}
return head;
}function ListNode(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
function deleteMiddle(head) {
if (!head || !head.next) return null;
let count = 0;
let temp = head;
while (temp) {
count++;
temp = temp.next;
}
let mid = Math.floor(count / 2);
temp = head;
let prev = null;
while (mid--) {
prev = temp;
temp = temp.next;
}
if (prev) {
prev.next = prev.next.next;
}
return head;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* deleteMiddle(struct ListNode* head) {
if (!head || !head->next) return NULL;
struct ListNode *temp = head;
int count = 0;
while (temp) {
count++;
temp = temp->next;
}
int mid = count / 2;
struct ListNode *prev = NULL;
temp = head;
while (mid-- > 0) {
prev = temp;
temp = temp->next;
}
if (prev && prev->next) {
prev->next = prev->next->next;
}
return head;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode DeleteMiddle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode temp = head;
int count = 0;
while (temp != null) {
count++;
temp = temp.next;
}
int mid = count / 2;
temp = head;
ListNode prev = null;
while (mid-- > 0) {
prev = temp;
temp = temp.next;
}
if (prev != null) {
prev.next = prev.next.next;
}
return head;
}
}This Python solution makes use of the ListNode class to represent each node. It calculates the length of the linked list, computes the position of the middle node, and then updates the links to remove it.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Approach 2: Two-Pointer Method
This approach uses two pointers: a slow pointer and a fast pointer. The fast pointer moves twice as fast as the slow pointer. When the fast pointer reaches the end, the slow pointer will be at the middle node. We can then remove the middle node in a single pass.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def deleteMiddle(self, head: ListNode) -> ListNode:
if not head or not head.next:
return None
slow = head
fast = head
prev = None
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
if prev:
prev.next = slow.next
return headclass ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
public ListNode deleteMiddle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head, fast = head, prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
if (prev != null) {
prev.next = slow.next;
}
return head;
}
}#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* deleteMiddle(ListNode* head) {
if (!head || !head->next) return nullptr;
ListNode* slow = head;
ListNode* fast = head;
ListNode* prev = nullptr;
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
if (prev) {
prev->next = slow->next;
}
return head;
}function ListNode(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
function deleteMiddle(head) {
if (!head || !head.next) return null;
let slow = head, fast = head;
let prev = null;
while (fast && fast.next) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
if (prev) {
prev.next = slow.next;
}
return head;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* deleteMiddle(struct ListNode* head) {
if (!head || !head->next) return NULL;
struct ListNode *slow = head, *fast = head;
struct ListNode *prev = NULL;
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
if (prev) {
prev->next = slow->next;
}
return head;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode DeleteMiddle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head, fast = head, prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
if (prev != null) {
prev.next = slow.next;
}
return head;
}
}In the Python solution, slow and fast pointers are used to find the middle node efficiently. The middle node is removed by adjusting pointers in a single list traversal.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Fast and Slow Pointers
The fast and slow pointer technique is a common method used to solve problems related to linked lists. We can maintain two pointers, a slow pointer slow and a fast pointer fast. Initially, slow points to a dummy node, whose next pointer points to the head node head of the list, while fast points to the head node head.
Then, we move the slow pointer one position backward and the fast pointer two positions backward each time, until the fast pointer reaches the end of the list. At this point, the node next to the node pointed by the slow pointer is the middle node of the list. We can remove the middle node by setting the next pointer of the node pointed by the slow pointer to point to the next next node.
The time complexity is O(n), where n is the length of the list. The space complexity is O(1).
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function deleteMiddle(head: ListNode | null): ListNode | null {
const dummy = new ListNode(0, head);
let [slow, fast] = [dummy, head];
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
slow.next = slow.next.next;
return dummy.next;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteMiddle(head *ListNode) *ListNode {
dummy := &ListNode{Val: 0, Next: head}
slow, fast := dummy, dummy.Next
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
}
slow.Next = slow.Next.Next
return dummy.Next
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pass Method | Time Complexity: O(n) |
| Approach 2: Two-Pointer Method | Time Complexity: O(n) |
| Fast and Slow Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass Method (Count then Delete) | O(n) | O(1) | When you want the simplest logic and explicit middle index |
| Two-Pointer Method (Fast & Slow) | O(n) | O(1) | Preferred interview solution using a single traversal |
Frequently asked questions
Is Delete the Middle Node of a Linked List easy or hard?
The problem is classified as Medium difficulty on LeetCode. The logic is simple once you know the fast–slow pointer pattern, but candidates must correctly manage pointer updates and edge cases such as a single-node list.
Delete the Middle Node of a Linked List Python/Java solution
In Python or Java, maintain fast and slow pointers starting at the head and track the previous node of slow. Advance fast by two nodes and slow by one node until fast reaches the end. Then update prev.next to skip the slow node. The implementation runs in O(n) time and O(1) space.
How to solve Delete the Middle Node of a Linked List in O(n)?
Use the fast and slow pointer technique. Initialize slow, fast, and a previous pointer. Move fast two nodes at a time and slow one node at a time while tracking the previous node of slow. When fast reaches the end, delete the middle by setting prev.next to slow.next. The list is processed once, giving O(n) time and O(1) space.
What is the best approach for Delete the Middle Node of a Linked List?
The two-pointer (fast and slow pointer) approach is the best solution. It finds the middle node in a single traversal by moving the fast pointer two steps and the slow pointer one step at a time. When the fast pointer reaches the end, the slow pointer is at the middle. This method runs in O(n) time with O(1) extra space.
Is Delete the Middle Node of a Linked List asked at Google/Amazon/Meta?
Linked list pointer manipulation problems are common in interviews at companies like Amazon, Google, and Meta. Variants such as finding the middle node, removing the Nth node from the end, or deleting nodes during traversal frequently appear in technical screens.
What data structure is used in Delete the Middle Node of a Linked List?
The problem uses a singly linked list. Each node contains a value and a pointer to the next node. Solving it efficiently relies on pointer traversal techniques such as the fast–slow two-pointer method.
What is the time complexity of Delete the Middle Node of a Linked List?
The time complexity is O(n) because the algorithm must traverse the linked list to reach the middle. The two-pass method performs two linear scans, while the fast–slow pointer method completes the task in a single pass. Both approaches use O(1) additional space.