009_Delete_Middle_of_Linkedlist.cpp

//{ Driver Code Starts
#include <bits/stdc++.h> 
using namespace std; 

struct Node
{
    int data;
    struct Node* next;
    
    Node(int x){
        data = x;
        next = NULL;
    }
};

/* Function to get the middle of the linked list*/
struct Node *deleteMid(struct Node *head);
void printList(Node* node) 
{ 
	while (node != NULL) { 
		cout << node->data <<" "; 
		node = node->next; 
	}  
	cout<<"\n";
} 
int main() 
{ 
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;

		int data;
		cin>>data;
		struct Node *head = new Node(data);
		struct Node *tail = head;
		for (int i = 0; i < n-1; ++i)
		{
			cin>>data;
			tail->next = new Node(data);
			tail = tail->next;
		}
		head = deleteMid(head);
		printList(head); 
	}
	return 0; 
} 



// } Driver Code Ends


/* Link list Node:

struct Node
{
    int data;
    struct Node* next;

    Node(int x){
        data = x;
        next = NULL;
    }
};

*/

// Deletes middle of linked list and returns head of the modified list
Node* deleteMid(Node* head)
{
    Node* q;
    Node* temp;
    int mid,count=0;
    for(q=head;q!=NULL;q=q->next)
    {
        count++;
    }
    
    if(count==0 ||count==1)
    {
        return NULL;
    }
    
    mid=int(count/2)+1;
    if(mid>0 && mid<=count)
    {
        q=head;
        for(int i=1;i<mid-1;i++)
        {
            q=q->next;
        }
        temp=q->next;
        q->next=temp->next;
        delete(temp);
        return head;
    }


}