Featured

TechBytes on Linux

This is a growing list of Linux commands which might come handy for the of Linux users. 1. Found out i had to set the date like this: ...

Tuesday, December 4, 2012

What is the optimum way to find the middle node in a single linked list using C?


What is the optimum way to find the middle node in a single linked list using C?


    There are two ways
Method 1
1- Iterate through the link list to find the number of nodes in it (say n)
2- Start from the root of the list and travel as far as n/2

The other method is a bit tricky
Method 2
1- Start with two pointers both pointing to root
2- Now make one traverse the link list one node at a time
3- Make the other traverse the link list 2 nodes at a time
At the time, the 2nd pointer reaches the end, the 1st pointer would only have reached the mid

The 1st method is optimized for memory and the 2nd one for concurrent traversal and speed

Popular Posts