dxmio.com

Today’s potential interview question is to reverse a linked list, without recursion. This one can be rather tough on the brain if you don’t think visually, but the basic idea here is to keep a pointer to:

• Keep a pointer to the next node so that you don’t lose a way to access it once you reverse the direction of the prior node’s ‘next’ pointer.
• Keep a pointer to the last node so that you have a way of pointing the current node back (the above is required so that you don’t lose where it formerly pointed.)
• ‘Inchworm’ your way forward in this manner until you’ve hit everything, and at the end repoint the head to be where you’re at.

Here’s the code (Note that NodePtr is simply a typedef of a boost::shared_ptr – it’s a ’smart’ pointer.):

void LinkedList::reverse()
{
	if((_head == NULL) || (_length == 1))
	{
		return;
	}
	else
	{
		NodePtr previous = NodePtr();
		NodePtr current = _head;
		NodePtr next = NodePtr();
		while(current)
		{
			next = current->next;
			current->next = previous;
			previous = current;
			current = next;
		}
 
		_head = previous;
 
	}
}