Delete Middle of linked list

There is an basic and commonly asked question for in linked list how to delete middle of given linked list in efficient manner. there of many solution of this problem.

We can be solve this problem of many way. first one is very simple approach count all number of linked list nodes and decide which node are exist in middle position. And after that visit middle node closest first node and delete that middle node. This process are tack O(n) time. but in this program there is need of to iterates 2 times of loops.

Before Delete Middle node

After Delete Middle node

Delete Middle node

If you are have deep knowledge of linked list, So we can solve this problem by single loop. In this process firstly need of two pointer variable. One pointer (p1) is initial point of first node of linked list. this pointer are incremented of two times of next linked list node, So this is fast pointer. And other pointer (p2) is slowly increment by one by one.

That means p1 and p2 is incremented by this p1->next->next and p2->next . When p1->next and p1->next->next are NULL so p2 are point to is pointed to middle of linked list. So we can remove linked list element by using of single loop. In below program is implemented solutions.

Note that in this linked list are 7 nodes. Then so 4'th position nodes is middle node of this linked list.

Conclusion

This program are working when linked list contain at least three nodes. because if node are less than 3 then there are not possible to find mid node.

And linked list are contain even number of nodes. assuming there are more than two nodes. Then in this case there are possible two middle nodes. Let take an example.

 1-->2-->3-->4-->5-->6-->NULL 

In this situation have 3rd and 4th position nodes are same priority of the mid position. So in this case both algorithm are valid to delete middle of 3rd position or 4th position nodes.



Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved