Linked list delete at mid

#1

plzz tell me the logic and code of delete at middle in a link list?

#2

#include

using namespace std;

class node{
public:
int data;
node* next;

node(int a){
	data = a;
	next = NULL;
}

};

void insertathead(node*&head,int data)
{
node*n= new node(data);
n->next=head;
head=n;
}

void deleteit(node*&head,int p)
{
int j =1;
nodetemp=head;
nodeprev=head;
node*midd=head;
while(j<p-1)
{
temp=temp->next;
prev=temp;
midd=temp;
j++;
}

temp=temp->next;
midd=temp;
temp=temp->next;

delete midd;
prev->next=temp;
return;

}

void print(nodehead)
{
nodetemp=head;
while(temp!=NULL)
{
cout<data<<" ";
temp=temp->next;
}
}

int main()
{
node* head = NULL;
insertathead(head,5);
insertathead(head,4);
insertathead(head,3);
insertathead(head,2);
insertathead(head,1);
insertathead(head,6);

deleteit(head,3);


print(head);

return 0;

}

plzz tell be a better optimisation of my code…

here midd is to be deleted…
temp is one ahead of that…
prev is one prior to mid…

#3

hi nikhil
We can delete middle node using one traversal. The idea is to use two pointers, slow_ptr and fast_ptr. Both pointers start from head of list. When fast_ptr reaches end, slow_ptr reaches middle
(Traverse linked list using two pointers. Move one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.)
The additional thing is to keep track of previous of middle so that we can delete middle.

1 Like
#4

hey @ynikhil1999, your logic is 90% correct here. You just have to make following changes

  1. run while loop one more time.
  2. Avoid extra temp=temp->next.

updated Code
void deleteit(node*&head,int p)
{
int j =1;
node temp=head;
node prev=head;
node *midd=head;
while(j<=p-1)
{
prev=temp;
temp=temp->next;

midd=temp;
j++;
}

temp=temp->next;
prev->next=temp;
delete midd;

//midd=temp;
//temp=temp->next;

return;
}

1 Like
#5

hey @ynikhil1999 , if your query is resolved. Please mark this doubt as resolved and rate me on the basis of your experience.
rating option will appear when to mark this doubt as resolved

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.