Given the head of a singly linked list, delete the middle node and return the head of the modified linked list.
For a linked list with length n, the middle node is present at index floor(n / 2) using zero-based indexing. A single-node linked list becomes empty after deletion.
Example 1
Input: head = [1, 3, 4, 7, 1, 2, 6]
Output: [1, 3, 4, 1, 2, 6]
Explanation: Length is 7, middle index is 3, and value 7 gets deleted.
Example 2
Input: head = [1, 2, 3, 4]
Output: [1, 2, 4]
Explanation: Length is 4, middle index is 2, and value 3 gets deleted.
Approach 1
First, we count the total number of nodes in the linked list. Using this length, we determine the position of the middle node and then traverse the list again to reach the node just before it. Finally, we remove the middle node by updating the previous node's next pointer.
Algorithm
Return
NULLwhen the linked list contains only one node, as removing its middle node leaves the list empty.Traverse the linked list once to count the total number of nodes, since the middle position depends on the list length.
Compute the middle position as
length / 2, as this identifies the node that needs to be removed according to the required indexing.Move a pointer to the node just before the middle node, since changing this node's
nextpointer is enough to bypass the middle node.Update the previous node's
nextpointer toprevious->next->next, which removes the middle node from the chain while keeping the remaining nodes connected.Return the original
head, as the first node remains unchanged after deleting the middle node.
Dry Run
delet middle node length count
Solution
#include <bits/stdc++.h>using namespace std;struct ListNode { int data; ListNode* next; ListNode(int value) { data = value; next = nullptr; }};class Solution {public: // Function to delete middle node using node count. ListNode* deleteMiddle(ListNode* head) { if (head == nullptr || head->next == nullptr) return nullptr; int length = 0; ListNode* current = head; // Count total nodes in linked list. while (current != nullptr) { length++; current = current->next; } int middleIndex = length / 2; ListNode* previous = head; // Move previous pointer to node before middle. for (int index = 0; index < middleIndex - 1; index++) { previous = previous->next; } // Bypass middle node. previous->next = previous->next->next; return head; }};// Function to create linked list from array.ListNode* createList(vector<int>& arr) { if (arr.empty()) return nullptr; ListNode* head = new ListNode(arr[0]); ListNode* current = head; for (int index = 1; index < (int)arr.size(); index++) { current->next = new ListNode(arr[index]); current = current->next; } return head;}// Function to print linked list values.void printList(ListNode* head) { ListNode* current = head; while (current != nullptr) { cout << current->data; if (current->next != nullptr) cout << " "; current = current->next; }}// Driver code.int main() { vector<int> arr = {1, 3, 4, 7, 1, 2, 6}; ListNode* head = createList(arr); Solution sol; head = sol.deleteMiddle(head); printList(head); return 0;}Complexity Analysis
Time Complexity: O(N), where N is the total number of nodes. One traversal counts the nodes, and another reaches the node before the middle.
Space Complexity: O(1), as only a few pointers and variables are used, regardless of N.
Approach 2
The slow and fast pointer technique finds the middle node in a single traversal. While the slow pointer moves one node at a time, the fast pointer moves two nodes at a time. A previous pointer is maintained to keep track of the node before the slow pointer, allowing the middle node to be removed directly once it is found.
Algorithm
Return
NULLwhen the linked list contains only one node, as removing its middle node leaves no nodes remaining.Initialize
slowandfastathead, andpreviousasNULL, whereslowis used to locate the middle whilefastmoves twice as quickly.Move
previoustoslow,slowone step forward, andfasttwo steps forward whilefastandfast->nextexist, as this makesslowreach the middle whenfastreaches the end.Update
previous->nexttoslow->next, which bypasses the middle node and keeps the remaining nodes connected.Return the original
head, as deleting the middle node does not change the head of the linked list.
Dry Run
delet middle
Solution
#include <bits/stdc++.h>using namespace std;struct ListNode { int data; ListNode* next; ListNode(int value) { data = value; next = nullptr; }};class Solution {public: // Function to delete middle node using slow and fast pointers. ListNode* deleteMiddle(ListNode* head) { if (head == nullptr || head->next == nullptr) return nullptr; ListNode* slow = head; ListNode* fast = head; ListNode* previous = nullptr; // Move fast twice as quickly as slow. while (fast != nullptr && fast->next != nullptr) { previous = slow; slow = slow->next; fast = fast->next->next; } // Bypass middle node tracked by slow pointer. previous->next = slow->next; return head; }};// Function to create linked list from array.ListNode* createList(vector<int>& arr) { if (arr.empty()) return nullptr; ListNode* head = new ListNode(arr[0]); ListNode* current = head; for (int index = 1; index < (int)arr.size(); index++) { current->next = new ListNode(arr[index]); current = current->next; } return head;}// Function to print linked list values.void printList(ListNode* head) { ListNode* current = head; while (current != nullptr) { cout << current->data; if (current->next != nullptr) cout << " "; current = current->next; }}// Driver code.int main() { vector<int> arr = {1, 3, 4, 7, 1, 2, 6}; ListNode* head = createList(arr); Solution sol; head = sol.deleteMiddle(head); printList(head); return 0;}Complexity Analysis
Time Complexity: O(N), where N is the total number of nodes. The slow and fast pointers find the middle in a single traversal.
Space Complexity: O(1), as only slow, fast, and previous pointers are used, regardless of N.
FAQs about Delete the middle node in Linked List
Q1. Which node gets deleted for even length linked lists?
The node at index floor(n / 2) gets deleted, so length 4 deletes index 2.
Q2. Can the middle node be deleted in one pass?
Yes. Slow and fast pointers locate the middle node during a single traversal.
Q3. Does a single-node linked list become empty?
Yes. Deleting the only node returns null.
Q4. Is extra memory required for the optimal method?
No. The optimal method uses only constant pointer variables.
Be the first to add a comment.