Given a singly linked list, delete the middle of the linked list. For example, if the given linked list is 1->2->3->4->5 then the linked list should be modified to 1->2->4->5
If there are even nodes, then there would be two middle nodes, we need to delete the second middle element. For example, if given linked list is 1->2->3->4->5->6 then it should be modified to 1->2->3->5->6.
If the input linked list is NULL, then it should remain NULL.
If the input linked list has 1 node, then this node should be deleted and a new head should be returned.
Simple solution: The idea is to first count the number of nodes in a linked list, then delete n/2’th node using the simple deletion process.
C++14
// C++ program to delete middle // of a linked list #include <bits/stdc++.h> using namespace std; // Link list Node struct Node { int data; struct Node* next; }; // Count of nodes int countOfNodes(struct Node* head) { int count = 0; while (head != NULL) { head = head->next; count++; } return count; } // Deletes middle node and returns // head of the modified list struct Node* deleteMid(struct Node* head) { // Base cases if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } struct Node* copyHead = head; // Find the count of nodes int count = countOfNodes(head); // Find the middle node int mid = count / 2; // Delete the middle node while (mid-- > 1) { head = head->next; } // Delete the middle node head->next = head->next->next; return copyHead; } // A utility function to print // a given linked list void printList(struct Node* ptr) { while (ptr != NULL) { cout << ptr->data << "->"; ptr = ptr->next; } cout << "NULL"; } // Utility function to create // a new node. Node* newNode(int data) { struct Node* temp = new Node; temp->data = data; temp->next = NULL; return temp; } // Driver code int main() { // Start with the empty list struct Node* head = newNode(1); head->next = newNode(2); head->next->next = newNode(3); head->next->next->next = newNode(4); cout << "Given Linked List"; printList(head); head = deleteMid(head); cout << "Linked List after deletion of middle"; printList(head); return 0; } |
Output:
Given Linked List 1->2->3->4->NULL Linked List after deletion of middle 1->2->4->NULL
Complexity Analysis:
- Time Complexity: O(n).
Two traversals of the linked list is needed - Auxiliary Space: O(1).
No extra space is needed.
Efficient solution:
Approach: The above solution requires two traversals of the linked list. The middle node can be deleted using one traversal. The idea is to use two pointers, slow_ptr, and fast_ptr. Both pointers start from the head of list. When fast_ptr reaches the end, slow_ptr reaches middle. This idea is same as the one used in method 2 of this post. The additional thing in this post is to keep track of the previous middle so the middle node can be deleted.
Below is the implementation.
C++
// C++ program to delete middle // of a linked list #include <bits/stdc++.h> using namespace std; // Link list Node struct Node { int data; struct Node* next; }; // Deletes middle node and returns // head of the modified list struct Node* deleteMid(struct Node* head) { // Base cases if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } // Initialize slow and fast pointers // to reach middle of linked list struct Node* slow_ptr = head; struct Node* fast_ptr = head; // Find the middle and previous // of middle. // To store previous of slow_ptr struct Node* prev; while (fast_ptr != NULL && fast_ptr->next != NULL) { fast_ptr = fast_ptr->next->next; prev = slow_ptr; slow_ptr = slow_ptr->next; } // Delete the middle node prev->next = slow_ptr->next; delete slow_ptr; return head; } // A utility function to print // a given linked list void printList(struct Node* ptr) { while (ptr != NULL) { cout << ptr->data << "->"; ptr = ptr->next; } cout << "NULL"; } // Utility function to create // a new node. Node* newNode(int data) { struct Node* temp = new Node; temp->data = data; temp->next = NULL; return temp; } // Driver code int main() { // Start with the empty list struct Node* head = newNode(1); head->next = newNode(2); head->next->next = newNode(3); head->next->next->next = newNode(4); cout << "Given Linked List"; printList(head); head = deleteMid(head); cout << "Linked List after deletion of middle"; printList(head); return 0; } |
Output:
Given Linked List 1->2->3->4->NULL Linked List after deletion of middle 1->2->4->NULL
Complexity Analysis:
- Time Complexity: O(n).
Only one traversal of the linked list is needed - Auxiliary Space: O(1).
As no extra space is needed.
Please refer complete article on Delete middle of linked list for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
