C++ 遞歸和非遞歸實現鏈表逆序

C++ 遞歸和非遞歸實現鏈表逆序

測試環境：vs2010 windows7

逆序分別采用遞歸調用和鏈表頭插法實現逆序。

具體代碼如下：

#include
#include
using namespace std;

class LinkList
{
private:
	struct Node
	{
		struct Node *next;
		int value;
	};
	Node *phead;
	void reverse_use_recursion(Node *pnode)
	{
		if(pnode==nullptr||pnode->next==nullptr)
		{
			phead=pnode;
			return;
		}
		reverse_use_recursion(pnode->next);
		pnode->next->next=pnode;
		pnode->next=nullptr;
	}
public:
	LinkList()
	{
		phead=nullptr;

	}
	void initLinkList()
	{
		cout<<初始化鏈表以-1結束<>tmp;
		while(tmp!=-1)
		{
			if(phead==nullptr)
			{
				phead=new Node;
				phead->next=nullptr;
				phead->value=tmp;
				ptmp=phead;
			}else
			{
				ptmp->next=new Node;
				ptmp=ptmp->next;
				ptmp->value=tmp;
				ptmp->next=nullptr;
			}
			cin>>tmp;
		}
	}
	void print()
	{
		Node *pnode=phead;
		while(pnode!=nullptr)
		{
			cout<value<next;
		}
	}
	void clear()
	{
		Node *pnode=phead;
		while(pnode!=nullptr)
		{
			Node *ptmp=pnode;
			pnode=pnode->next;
			delete ptmp;
		}
		phead=nullptr;
	}
	void reverse_recursion()//采用遞歸逆序
	{
		Node *pnode=phead;
		reverse_use_recursion(pnode);
	}
	void reverse_recycle()//采用鏈表的頭插入法實現逆序
	{
		Node *pnode=phead;
		phead=nullptr;
		Node *ptmp;
		while(pnode!=nullptr)
		{
			if(phead==nullptr)
			{
				phead=pnode;
				ptmp=pnode;
				pnode=pnode->next;
				ptmp->next=nullptr;
			}
			else
			{
				ptmp=phead;
				phead=pnode;
				pnode=pnode->next;
				phead->next=ptmp;
				
			}

		}

	}
	~LinkList()
	{
		this->clear();
	}

};

int main()
{
	LinkList li;
	li.initLinkList();
	li.print();
	li.reverse_recycle();
	li.print();
	li.reverse_recursion();
	li.print();

	system(pause);
	return 0;
}