top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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

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

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button

3 Answers

+2 votes

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 by Salil Agrawal
+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 by Joy Dutta
0 votes
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 by Rajan Paswan
Similar Questions
+3 votes

How to delete the node that given as argument in single linked list?
Is there any system call to get prev pointer ?

Note: Here the goal is to delete the address not the node's value

+2 votes

I am looking for sample code which can impress an interviewer.

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...