2095. Delete the Middle Node of a Linked List LeetCode Solution
In this guide, you will get 2095. Delete the Middle Node of a Linked List LeetCode Solution with the best time and space complexity. The solution to Delete the Middle Node of a Linked List problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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 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, and 5, the middle nodes are 0, 1, 1, 2, and 2, 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.
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
2095. Delete the Middle Node of a Linked List LeetCode Solution in C++
class Solution {
public:
ListNode* deleteMiddle(ListNode* head) {
ListNode dummy(0, head);
ListNode* slow = &dummy;
ListNode* fast = &dummy;
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
// Delete the middle node.
slow->next = slow->next->next;
return dummy.next;
}
}; /* code provided by PROGIEZ */
2095. Delete the Middle Node of a Linked List LeetCode Solution in Java
class Solution {
public ListNode deleteMiddle(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode slow = dummy;
ListNode fast = dummy;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Delete the middle node.
slow.next = slow.next.next;
return dummy.next;
}
} // code provided by PROGIEZ
2095. Delete the Middle Node of a Linked List LeetCode Solution in Python
class Solution:
def deleteMiddle(self, head: ListNode | None) -> ListNode | None:
dummy = ListNode(0, head)
slow = dummy
fast = dummy
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Delete the middle node.
slow.next = slow.next.next
return dummy.next # code by PROGIEZ
