首页 > 资讯 > 其他综合 > 正文

链表的逆置

17-04-19 来源：[db:作者]

收藏我要投稿

链表的逆置：输入一个链表的头节点，从头到尾反过来打印出每个节点的值。

Reverse()函数：输入头结点，可输出的确是从尾到头；即第一个输入的节点，最后一个输出；最后一个输入的结点，第一个输出；很典型的“后进先出“；用桟实现；

1、将结点放进桟中，当结点全遍历一遍时，链表已经反过来，

2、此时再从桟顶逐个输出结点的值

Reverse2()函数：递归本质就是桟结构；则用_Reverse2(_head)函数去递归；Reverse2()函数自己递归不了自己，参数传不进去，则调用了另外一个函数_Reverse2(_head)；

Reverse3()函数：递归的代码是简单明了，但是当结点很多时，需要递归的层就太深了，效率就很低，所以用循环去实现；//摘结点；如下图1：

addLinkNode()函数：增加链表的结点；

deleteLinkNode()函数：删除某一个值为value的结点；

Print()函数：用循环去逆置时，才用此函数去打印；

测试用例：

Test()：测试的是Reverse();

Test2()：测试的是Reverse2();

Test3()：测试的是Reverse3();

三个测试用例的数据都为：3->4->5->7；则结果也都相同，为：7->5->4->3

代码如下：

#include
#include
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 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;
}

结果如下：

点击复制链接与好友分享!回本站首页