反转单向链表的四种实现（递归与非递归，C++）

单项链表的反转指的是这样一类问题：给定一个单项链表的头指针 head，写一个算法，将其反转，并返回新的头指针 head’。

本文给出了这一问题的两种解法，分别是递归解法和非递归解法。

递归解法一

递归解法一的思路如下。

定义一个方法 reserve1inner (node *element, node *prev)，用来反转指定的节点。

这个方法使用如下办法执行：先反转这个节点的后续节点，然后再反转自己。

所谓「反转自己」，就是指将自己的next字段的值改成prev（上一个节点的指针）的值。也就是说，把本来指向后面一个节点地址的next字段改为指向前一个节点地址的prev字段。

这个思路里有两点需要注意：

**为什么要提供 prev 参数？**单项链表中是只有后续节点的地址的，因此当反转 element 的时候，必须手工提供 prev 参数。通过递归，这个参数正好由其前一项调用时提供。第一次调用时，这个参数由 reserve1 函数直接提供 nullptr。
如何得到新的 head’的值？head’的值只有当遍历到最后一个节点时才会获得，因此需要回传。所以将递归方法增加了一个返回值，返回值就定义为新的head’的指针值。获取这个值的方法是，直接返回下一层递归的值即可，除非，已经是最后一层，此时应返回自身。

递归解法二

递归解法二的思路如下。

定义一个方法 reserve (node *element)，用来反转指定的节点。

这个方法和解法一不同：直观上看少了一个参数 prev，本质上看，函数的定义不同。第二个解法其实是一种「拼接」的算法：将老的链表扭断，逐步拼到新的链表上去。（可以参考非递归解法二的说明）第一个解法要把它和上一个相连（prev），第二个解法只把它自己反转完，前一个节点直接设置为 nullptr。也就是说，在这个方法执行完后，如果element 不是第一个节点，那么这个节点会和它前面的节点断开。

下面是本解法的主要步骤：

如果 element 是唯一的元素（element 的下一个为空），则直接返回 element。（element 就是它本身的头指针）
如果不是，那么先反转 element 的 next，并将返回值保存为 ptrHeadNext（反转之后，其实这里面存储的是原来最后一个的指针）。
将 element 拼接在新反转的元素之后，利用 ptrHeadNext。（此处目前其实存储的是反转后尾部）

非递归解法一

非递归解法的思路是遍历。

针对每一个节点，指针为 ptrCurrent，都进行一次处理。
处理的时候，都是将这个节点的next设置为上一次处理的 ptrCurrent（此时已经保存为 prev）。
初始化的时候，先将第一个 ptrCurrent 反转后设置的 prev 定义为 nullptr。

非递归解法二

我们也可以有一种更清晰的思路来求解。主要思想是，重新拼接新的链表（而不是直接修改老链表）。也就是说，我们执行如下步骤：

创建一个反转后的链表，设置其头为ptrReserved。
每次都从老的链表里，取出第一个元素，并加入到新链表的第一个的位置（此步完成了反转）。
直到所有元素都被加入到 ptrReserved 中。

针对每一个节点，指针为 ptrCurrent，都进行一次处理。
处理的时候，都是将这个节点的next设置为上一次处理的 ptrCurrent（此时已经保存为 prev）。
初始化的时候，先将第一个 ptrCurrent 反转后设置的 prev 定义为 nullptr。

注释

nullptr 是 C++11 标准中新定义的「空指针」类型，然而目前很多编译器还不能识别。nullptr 非常好用，因为它很好地区分了 0 和空指针这两种不同的值（其实从本质上来说，它本是一种值）。以往使用的 NULL，null 等并不是 C++ 标准，而 nullptr 的到来很好的解决了这个问题。目前，也可以使用 define 宏来模拟。（但这并不是全等的模拟，具体请参考 C++11 的相关定义。）
注意到在递归的 reserve1inner 算法中，返回值前增加了一个 typename。这是 C++ 标准规定的反歧义语法，当使用模板类的嵌入类型时，必须增加 typename 关键字才能当作类型，否则会当作成员变量。当然，你也可以使用 typedef 去掉讨厌的 typename。

实现

下面分别是两种解法的实现代码（第一个是递归解法1，第二个是非递归解法1）。（代码中所引用的 ceeji::stack 类型的定义见这里。在本文中 stack 没有意义，有意义的只是其中的链表而已。）

template void stack::reserve1() {
	this->head = reserve1inner(this->head, nullptr);
}

template typename stack::node* stack::reserve1inner(stack::node *element, stack::node *prev) {
	node *ret;
	if (element->next != nullptr) {
		ret = reserve1inner(element->next, element);
	}
	else
		ret = element;

	element->next = prev;

	return ret;
}

template void stack::reserve2() {
	node *ptrCurrent = this->head;
	node *prev = nullptr, *next;

	while (ptrCurrent != nullptr) {
		next = ptrCurrent->next;
		ptrCurrent->next = prev;
		prev = ptrCurrent;

		ptrCurrent = next;
	}

	this->head = prev;
}

递归解法一

递归解法二

非递归解法一

非递归解法二

注释

实现

猜你喜欢