算法导论：10.2-7 给出一个 O(n) 时间的非递归过程，实现对一个含有 n 个元素的单链表的逆转。要求除存储链表本身所需的空间外，该过程只能使用固定大小的存储空间。

#ifndef _SINGLY_LINKED_LIST_H
#define _SINGLY_LINKED_LIST_H

/***********************************************************
10.2-7 单链表类，并实现了在 O(n) 时间内链表的逆转
************************************************************/

template <class T>
class SinglyLinkedList
{
public:
	// 一个表示链表结点的数据结构
	class Node{
	public:
		// 只有 StackUseSinglyLinkedList 才可以构造这个类型的对象
		// 访问这个类型的私有成员
		friend class SinglyLinkedList < T > ;
		// 结点的值
		T value;
	private:
		// 默认构造函数，要求类型 T 也要有默认构造函数
		Node() :_next(nullptr){}
		// 将构造函数设置为私有的，防止在外部创建这个类型的对象
		Node(const T& e) :_next(nullptr), value(e){}
		// 指向下一个元素，如果这个值为空，
		// 表示本结点是链表中的最后一个元素
		Node* _next;
	};

	SinglyLinkedList();
	~SinglyLinkedList();

	// 测试链表是否为空，空链表的头结点的 _next 为空
	bool empty() const { return _head->_next == nullptr; }

	void insert(const T&);

	void remove(const T&);

	Node* search(const T&) const;

	// 将链表内的结点逆转，并返回当前链表
	SinglyLinkedList* reverse();

	void print() const;
private:
	Node* _head;
};

template <class T>
SinglyLinkedList<T>::SinglyLinkedList()
{
	// 为头结点分配空间
	_head = new Node();
}

template <class T>
typename SinglyLinkedList<T>::Node* SinglyLinkedList<T>::search(const T& element) const{
	// 从链表头开始搜索再回到链表头
	auto node = _head->_next;
	while (node){
		if (node->value =http://www.mamicode.com/= element) return node;>

单链表的逆转