Given a single linked list, how do you find the middle of the list?
One simple method is to traverse through the list twice once to find it’s length, and second to navigate to the middle of the list by traversing length/2 nodes. Even though this method runs in O(n) time, there is still a chance of improving this method.
In this method we traverse the list only once. We take two pointers, one, a slow pointer which will advance one node at a time; and a fast pointer which will advance two nodes at a time. we iterate through the list until the fast pointer reaches the end of the list. At this stage, the slow pointer would be pointing to the middle of the linked list.
Following is the C++ function which implements this method. For working program please visit this post.
One simple method is to traverse through the list twice once to find it’s length, and second to navigate to the middle of the list by traversing length/2 nodes. Even though this method runs in O(n) time, there is still a chance of improving this method.
In this method we traverse the list only once. We take two pointers, one, a slow pointer which will advance one node at a time; and a fast pointer which will advance two nodes at a time. we iterate through the list until the fast pointer reaches the end of the list. At this stage, the slow pointer would be pointing to the middle of the linked list.
Following is the C++ function which implements this method. For working program please visit this post.
SLLNode* getMiddle()
{
//if the list is empty or has a single node; return head
if( head == NULL || head->getNext() == NULL )
return head;
SLLNode *slow = head;
SLLNode *fast = head->getNext();
while( fast != NULL )
{
//move fast pointer two steps ahead
if( fast->getNext() != NULL )
{
fast = fast->getNext()->getNext();
}
else
break;
//move slow pointer one step
slow = slow->getNext();
}
return slow;
}