   # Data Structure: What is the efficient way to delete middle node of a singly linked list ?

+1 vote
365 views
Data Structure: What is the efficient way to delete middle node of a singly linked list ? posted May 18, 2014

This jobs can be done once you are able to find out the middle node of the Link List. Assuming the link list is single link list we can follow the following algo -
1. Take two pointers slow_ptr and fast_ptr.
2. make fast_ptr move two nodes in slow_ptr moves one node in each iteration more than slow *ptr.
3. when fast_ptr reaches to null then slow_ptr will point to middle node and you can delete it.

``````Void deleteMidddle(Node* head)
{
Node* slow_ptr = head;
Node* fast_ptr = head;
Node* tmp = head;
while(slow_ptr->next != NULL && fast_ptr->next != NULL)
{
tmp = slow_ptr;
slow_ptr = slow_ptr->next;
fast_ptr = fast_ptr->next->next;
}
tmp->next = slow_ptr->next;
free(slow_ptr);
}
`````` answer May 18, 2014
+1 vote

1.assign a fast *ptr and slow *ptr.
2.make fast *ptr to move 2nodes more than slow *ptr..
3.when fast *ptr ends to last node,then we see slow *ptr wiil be at middle.. answer May 18, 2014
``````Void deleteMidddleInLL(Node* start)
{
Node* slow_ptr = start;
Node* fast_ptr = start;
Node* temp = start;
while(slow_ptr->next != NULL && fast_ptr->next != NULL)
{
temp = slow_ptr;
slow_ptr = slow_ptr->next;
fast_ptr = fast_ptr->next->next;
}
temp->next = slow_ptr->next;
free(slow_ptr);
}
`````` answer Mar 20, 2016
Similar Questions