链表的逆置

#include<iostream>
#include<stack>
using namespace std;
struct LinkNode
{
	int _value;
	LinkNode* _next;

	LinkNode(int value = 0)
		:_value(value), _next(NULL)
	{}
};

class Link
{
private:
	void _Release()
	{
		while(_head != NULL)
		{
			LinkNode* begin = _head;
			_head = _head->_next;
			delete[] begin;
		}
	}
	void _ReverseLink2(LinkNode* &_head)
	{
		if (_head)
		{
			if (_head->_next)
			{
				_ReverseLink2(_head->_next );
			}
			cout << _head->_value << "->";
		}
	}

public:
	Link()
		:_head(NULL)
	{}

	~Link()
	{
		_Release();
	}

	void addLinkNode(int value)
	{
		//尾插
		//1.链表为空时
		//2.链表不为空时
		if (_head == NULL)
		{
			_head = new LinkNode(value);
		}
		else
		{
			LinkNode* tmp = new LinkNode(value);
			LinkNode* begin = _head;
			while (begin->_next != NULL)
			{
				begin = begin->_next;
			}
			begin->_next = tmp;
		}
	}

	void deleteLinkNode(int value)
	{
		//1.链表为空
		//2.链表的头结点
		//3.链表的尾节点
		//4.链表的倒数第二个节点
		//5.链表的中间
		if (_head == NULL)
		{
			cout << "Link is NULL!" << endl;
			return;
		}
		LinkNode* begin = _head;
		while (begin->_next != NULL && begin->_value != value)
			begin = begin->_next;
		if (begin->_next == NULL)
		{
			cout << "No Node!" << endl;
			return;
		}
		if (begin == _head)
		{
			_head = _head->_next;
			delete[] begin;
		}
		else if (begin->_next == NULL)
		{
			delete[] begin;
			begin = NULL;
		}
		else
		{
			begin->_value = begin->_next->_value;
			if (begin->_next->_next == NULL)
			{
				delete[] begin->_next;
				begin->_next = NULL;
			}
			else
			{
				LinkNode* tmp = begin->_next;
				begin->_next = begin->_next->_next;
				delete[] tmp;
			}
		}
	}
	void ReverseLink()
	{
		stack<LinkNode*> node;
		LinkNode* begin = _head;
		while (begin)
		{
			node.push(begin);
			begin = begin->_next;
		}
		while (!node.empty())
		{
			cout << node.top()->_value << "->";
			node.pop();
		}
		cout << endl;
	}
	void ReverseLink2()
	{
		_ReverseLink2(_head);
	}
	void ReverseLink3()
	{
		//摘结点
		LinkNode* begin = _head;
		LinkNode* tmp = _head;
		LinkNode* newHead = NULL;
		while (begin)
		{
			begin = begin->_next;
			tmp->_next = newHead;
			newHead = tmp;
			tmp = begin;
		}
		_head = newHead;
	}

	void Print()
	{
		LinkNode* begin = _head;
		while (begin)
		{
			cout << begin->_value << "->";
			begin = begin->_next;
		}
		cout << endl;
	}

private:
	LinkNode* _head;
};

void Test()
{
	cout << "Test:" << endl;
	Link LK;
	LK.addLinkNode(2);
	LK.addLinkNode(3);
	LK.addLinkNode(4);
	LK.addLinkNode(5);
	LK.addLinkNode(6);
	LK.addLinkNode(7);
	LK.Print();

	LK.deleteLinkNode(2);
	LK.deleteLinkNode(6);
	LK.Print();

	LK.ReverseLink();
}

void Test2()
{
	cout << "Test2:" << endl;
	Link LK;
	LK.addLinkNode(2);
	LK.addLinkNode(3);
	LK.addLinkNode(4);
	LK.addLinkNode(5);
	LK.addLinkNode(6);
	LK.addLinkNode(7);
	LK.Print();

	LK.deleteLinkNode(2);
	LK.deleteLinkNode(6);
	LK.Print();

	LK.ReverseLink2();
}

void Test3()
{
	cout << "Test3:" << endl;
	Link LK;
	LK.addLinkNode(2);
	LK.addLinkNode(3);
	LK.addLinkNode(4);
	LK.addLinkNode(5);
	LK.addLinkNode(6);
	LK.addLinkNode(7);
	LK.Print();

	LK.deleteLinkNode(2);
	LK.deleteLinkNode(6);
	LK.Print();

	LK.ReverseLink3();
	LK.Print();
}


int main()
{
	Test();
	Test2();
	cout << endl;
	Test3();
	return 0;
}