Delete middle of linked list
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.
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; }; // 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\n" ; } // 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 program to test above function*/ 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\n" ; printList(head); head = deleteMid(head); cout << "Linked List after deletion of middle\n" ; printList(head); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
C
// C program to delete middle of a linked list #include <stdio.h> #include <stdlib.h> /* Link list Node */ typedef struct Node { int data; struct Node* next; } Node; // count of nodes int countOfNodes(Node* head) { int count = 0; while (head != NULL) { head = head->next; count++; } return count; } // Deletes middle node and returns // head of the modified list Node* deleteMid(Node* head) { // Base cases if (head == NULL) return NULL; if (head->next == NULL) { free (head); return NULL; } 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(Node* ptr) { while (ptr != NULL) { printf ( "%d ->" , ptr->data); ptr = ptr->next; } printf ( "NULL\n" ); } // Utility function to create a new node. Node* newNode( int data) { Node* temp = (Node*) malloc ( sizeof (Node)); temp->data = data; temp->next = NULL; return temp; } /* Driver program to test above function*/ int main() { /* Start with the empty list */ Node* head = newNode(1); head->next = newNode(2); head->next->next = newNode(3); head->next->next->next = newNode(4); printf ( "Given Linked List\n" ); printList(head); head = deleteMid(head); printf ( "Linked List after deletion of middle\n" ); printList(head); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java program to delete middle // of a linked list import java.io.*; class GFG { /* Link list Node */ static class Node { int data; Node next; } // Utility function to create a new node. static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.next = null ; return temp; } // count of nodes static int countOfNodes(Node head) { int count = 0 ; while (head != null ) { head = head.next; count++; } return count; } // Deletes middle node and returns // head of the modified list static Node deleteMid(Node head) { // Base cases if (head == null ) return null ; if (head.next == null ) { return null ; } 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 static void printList(Node ptr) { while (ptr != null ) { System.out.print(ptr.data + "->" ); ptr = ptr.next; } System.out.println( "NULL" ); } /* Driver code*/ public static void main(String[] args) { /* Start with the empty list */ Node head = newNode( 1 ); head.next = newNode( 2 ); head.next.next = newNode( 3 ); head.next.next.next = newNode( 4 ); System.out.println( "Given Linked List" ); printList(head); head = deleteMid(head); System.out.println( "Linked List after deletion of middle" ); printList(head); } } // This code is contributed by rajsanghavi9. |
Python3
# Python3 program to delete middle # of a linked list # Link list Node class Node: def __init__( self ): self .data = 0 self . next = None # Count of nodes def countOfNodes(head): count = 0 while (head ! = None ): head = head. next count + = 1 return count # Deletes middle node and returns # head of the modified list def deleteMid(head): # Base cases if (head = = None ): return None if (head. next = = None ): del head return None copyHead = head # Find the count of nodes count = countOfNodes(head) # Find the middle node mid = count / / 2 # Delete the middle node while (mid > 1 ): 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 def printList(ptr): while (ptr ! = None ): print (ptr.data, end = '->' ) ptr = ptr. next print ( 'NULL' ) # Utility function to create a new node. def newNode(data): temp = Node() temp.data = data temp. next = None return temp # Driver Code if __name__ = = '__main__' : # Start with the empty list head = newNode( 1 ) head. next = newNode( 2 ) head. next . next = newNode( 3 ) head. next . next . next = newNode( 4 ) print ( "Given Linked List" ) printList(head) head = deleteMid(head) print ( "Linked List after deletion of middle" ) printList(head) # This code is contributed by rutvik_56 |
C#
// C# program to delete middle of a linked list using System; class GfG { /* Link list Node */ class Node { public int data; public Node next; } // count of nodes static int countOfNodes(Node head) { int count = 0; while (head != null ) { head = head.next; count++; } return count; } // Deletes middle node and returns // head of the modified list static Node deleteMid(Node head) { // Base cases if (head == null ) return null ; if (head.next == null ) { return null ; } // Initialize slow and fast pointers // to reach middle of linked list 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 static void printList(Node ptr) { while (ptr != null ) { Console.Write(ptr.data + "->" ); ptr = ptr.next; } Console.WriteLine( "NULL" ); } // Utility function to create a new node. static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.next = null ; return temp; } /* Driver code*/ public static void Main(String[] args) { /* Start with the empty list */ Node head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); Console.WriteLine( "Given Linked List" ); printList(head); head = deleteMid(head); Console.WriteLine( "Linked List after " + "deletion of middle" ); printList(head); } } /* This code is contributed by ShubhamSingh */ |
Javascript
<script> // Javascript program to delete the // middle of a linked list /* Link list Node */ class Node { constructor() { this .data = 0; this .next = null ; } } // count of nodes function countOfNodes(head) { let count = 0; while (head != null ) { head = head.next; count+=1; } return count; } // Deletes middle node and returns // head of the modified list function deleteMid(head) { // Base cases if (head == null ) return null ; if (head.next == null ) { return null ; } var copyHead = head; // Find the count of nodes var count = countOfNodes(head); // Find the middle node var mid = parseInt(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 function printList( ptr) { while (ptr != null ) { document.write(ptr.data + "->" ); ptr = ptr.next; } document.write( "NULL<br/>" ); } // Utility function to create a new node. function newNode(data) { temp = new Node(); temp.data = data; temp.next = null ; return temp; } /* Driver code */ /* Start with the empty list */ head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); document.write( "Given Linked List<br/>" ); printList(head); head = deleteMid(head); document.write( "Linked List after deletion of middle<br/>" ); printList(head); // This code is contributed by Shubham singh </script> |
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 are 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 the 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\n" ; } // 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 program to test above function*/ 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\n" ; printList(head); head = deleteMid(head); cout << "Linked List after deletion of middle\n" ; printList(head); return 0; } |
Java
// Java program to delete the // middle of a linked list class GfG { /* Link list Node */ static class Node { int data; Node next; } // Deletes middle node and returns // head of the modified list static Node deleteMid(Node head) { // Base cases if (head == null ) return null ; if (head.next == null ) { return null ; } // Initialize slow and fast pointers // to reach middle of linked list Node slow_ptr = head; Node fast_ptr = head; // Find the middle and previous of middle. Node prev = null ; // To store previous of slow_ptr 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; return head; } // A utility function to print // a given linked list static void printList(Node ptr) { while (ptr != null ) { System.out.print(ptr.data + "->" ); ptr = ptr.next; } System.out.println( "NULL" ); } // Utility function to create a new node. static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.next = null ; return temp; } /* Driver code*/ public static void main(String[] args) { /* Start with the empty list */ Node head = newNode( 1 ); head.next = newNode( 2 ); head.next.next = newNode( 3 ); head.next.next.next = newNode( 4 ); System.out.println( "Given Linked List" ); printList(head); head = deleteMid(head); System.out.println( "Linked List after deletion of middle" ); printList(head); } } // This code is contributed by Prerna saini. |
Python3
# Python3 program to delete the # middle of a linked list # Linked List Node class Node: def __init__( self , data): self .data = data self . next = None # Create and handle list operations class LinkedList: def __init__( self ): # Head of the list self .head = None # Add new node to the list end def addToList( self , data): newNode = Node(data) if self .head is None : self .head = newNode return last = self .head while last. next : last = last. next last. next = newNode # Returns the list in string format def __str__( self ): linkedListStr = "" temp = self .head while temp: linkedListStr + = str (temp.data) + "->" temp = temp. next return linkedListStr + "NULL" # Method deletes middle node def deleteMid( self ): # Base cases if ( self .head is None or self .head. next is None ): return # Initialize slow and fast pointers # to reach middle of linked list slow_Ptr = self .head fast_Ptr = self .head # Find the middle and previous of middle prev = None # To store previous of slow pointer while (fast_Ptr is not None and fast_Ptr. next is not None ): fast_Ptr = fast_Ptr. next . next prev = slow_Ptr slow_Ptr = slow_Ptr. next # Delete the middle node prev. next = slow_Ptr. next # Driver code linkedList = LinkedList() linkedList.addToList( 1 ) linkedList.addToList( 2 ) linkedList.addToList( 3 ) linkedList.addToList( 4 ) print ( "Given Linked List" ) print (linkedList) linkedList.deleteMid() print ( "Linked List after deletion of middle" ) print (linkedList) # This code is contributed by Debidutta Rath |
C#
// C# program to delete middle of a linked list using System; class GfG { /* Link list Node */ class Node { public int data; public Node next; } // Deletes middle node and returns // head of the modified list static Node deleteMid(Node head) { // Base cases if (head == null ) return null ; if (head.next == null ) { return null ; } // Initialize slow and fast pointers // to reach middle of linked list Node slow_ptr = head; Node fast_ptr = head; // Find the middle and previous of middle. Node prev = null ; // To store previous of slow_ptr 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; return head; } // A utility function to print // a given linked list static void printList(Node ptr) { while (ptr != null ) { Console.Write(ptr.data + "->" ); ptr = ptr.next; } Console.WriteLine( "NULL" ); } // Utility function to create a new node. static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.next = null ; return temp; } /* Driver code*/ public static void Main(String[] args) { /* Start with the empty list */ Node head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); Console.WriteLine( "Given Linked List" ); printList(head); head = deleteMid(head); Console.WriteLine( "Linked List after" + "deletion of middle" ); printList(head); } } /* This code is contributed by 29AjayKumar */ |
Javascript
<script> // Javascript program to delete the // middle of a linked list /* Link list Node */ class Node { constructor() { this .data = 0; this .next = null ; } } // Deletes middle node and returns // head of the modified list function deleteMid( head) { // Base cases if (head == null ) return null ; if (head.next == null ) { return null ; } // Initialize slow and fast pointers // to reach middle of linked list var slow_ptr = head; var fast_ptr = head; // Find the middle and previous of middle. var prev = null ; // To store previous of slow_ptr 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; return head; } // A utility function to print // a given linked list function printList( ptr) { while (ptr != null ) { document.write(ptr.data + "->" ); ptr = ptr.next; } document.write( "NULL<br/>" ); } // Utility function to create a new node. function newNode(data) { temp = new Node(); temp.data = data; temp.next = null ; return temp; } /* Driver code */ /* Start with the empty list */ head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); document.write( "Given Linked List<br/>" ); printList(head); head = deleteMid(head); document.write( "Linked List after deletion of middle<br/>" ); printList(head); // This code contributed by umadevi9616 </script> |
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.
Contact Us