Checks if a list is a palindrome.

linked_list_is_palindrome.cpp

template<typename Node>
bool _is_palindrome(Node* left, Node*& right, bool& move_back)
{
	if (left != right)
	{
		if (! _is_palindrome(left->next, right, move_back)) return false;
	}
	
	if (! move_back)
	{
		if (left->data != right->data) return false;
		
		right = right->next;
	}
	
	else move_back = false;
	
	return true;

}

template<typename Node>
bool is_palindrome(Node* node)
{
	if (! node || ! node->next) return false;
	
	auto turtle = node;
	auto hare = node;
	
	std::size_t count = 0;
	
	while (hare)
	{
		turtle = turtle->next;
		hare = hare->next->next;
		
		++count;
	}
	
	bool move_back = count % 2 == 0;
	
	return _is_palindrome(node, turtle, move_back);
}