链表反转的四种方法（栈、头插法、三指针法、递归法）

单链表反转或转置的四种方法

链表的反转实质上是反转链表上的内容：
若链表存储的数据是：1->2->3->4->5;
那么反转后则是：5->4->3->2->1;

下面来介绍链表反转的4种方法：（数据用1->2->3来表示，反转后则是3->2->1）

1.通过栈来实现

总体思路是：
1.先让链表中的内容依次进栈，用栈记录链表中的内容
2.接着依次出栈，更新链表中的数据即可
3.这种方法的思路简答，易于理解，但空间复杂度为O(n)，时间复杂度为O(n)，空间复杂度较大，不建议使用。
代码实现：

void translateLinklist(Linklist& L)
{
	stack<int> stk;//定义栈
	
	Linklist p = L->next;
	while (p)  //依次读取栈的内容，也就是第一步
	{
		stk.push(p->data);
		p = p->next;
	}

	p = L->next;
	while (p)   //依次出栈，更换链表中的数据，也就是第二步
	{
		p->data = stk.top();
		stk.pop();
		p = p->next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.头插法

头插，意思就是把结点依次放到头节点的下一个位置。
为什么头插可以实现链表的反转呢？
试想一下，我们把链表的每个节点（头节点除外），按顺序一个一个地放到头节点的后面，那么不就可以实现链表的反转了吗？（如图所示）

1. 使用临时变量 r 来实现当前节点的头插；
2. 接着用临时变量 p 来记录r->next, 即头插位置的下一个元素，从而可以找到下一个头插的元素。
3. 空间复杂度O(1)，时间复杂度O(n)

代码实现：

void translateLinklist(Linklist& L)  //头插法实现链表的反转
{
	Linklist p;			//用于记录p接下来的位置 
	Linklist r;			//记录p的位置进行头插
	p = L->next;		//用p来记录头节点以后的内容
	L->next = NULL;		//先将链表的头节点置空
	while (p)
	{
		r = p;			//用r来记录当前p的位置
		p = p->next;    //用p来不断地进行查找下一个元素
		r->next = L->next; //进行头插
		L->next = r;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.三指针法（也叫就地反转法）

三指针：
Linklist cur : 记录当前的节点;
Linklist pre : 记录当前节点的上一个节点;
Linklist r : 记录当前节点的下一个节点（即剩下的节点）;
在链表反转的过程中，我们只要让当前节点 cur 指向上一个节点pre ，是不是就大体上实现了这两个节点的反转了?
对，就是这样，那么怎么实现全部的节点反转呢？
这就简单了，当我们cur 指向pre 后，我们让上一个节点 pre 的位置移到 cur 这里，再把 cur 移到它下一个节点，那怎么记录它下一个节点呢，我们之前不是用 r 来记录的吗，就让 cur 移到 r 的位置就行了。
这样依次循环下去，最后再把头节点的指针指向 cur 就行了，就实现了链表的反转了。(如图所示)

注意事项：

1. 最后一定要让头节点的指针域指向pre，因为此时 cur为空。
2. 一定要先让 cur 指向 pre, 即转方向。再让pre 移到cur 的位置，即向后移。
3. 一定要先用 r 记录 cur的下一个节点，才有最后的cur 指向 r ，也就是 cur的下一个节点。
4. 空间复杂度O(1), 时间复杂度O(n)。

代码实现：

void translateLinklist(Linklist& L) //三指针法实现链表的反转
{
	Linklist pre;	// 记录之前的结点
	Linklist cur;	// 记录当前的结点
	Linklist r;		// 记录剩下的结点

	pre = NULL;		 //要先pre指针置为空
	cur = L->next;   //指向第一个结点
	while (cur)
	{
		r = cur->next;  //这样r不会成为野指针,且这一步一定要在最前面。即当cur不为空的时候才指向下一个
		cur->next = pre; //转方向
		pre = cur;      //往后移
		cur = r;
	}
	//结束后cur为空，所以L->next要指向pre;
	L->next = pre;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4. 递归法

递归的目的是要找到最后一个节点的位置，然后从最后一个节点开始，不断改变最后一个节点和其上一个节点的位置关系，即可。(如图)

注意事项：

1. 递归的时候无法删除头节点，所以递归法适合用于没有头节点的链表的反转，这也是递归法的一个弊端;
2. 要用新的头节点记录最后一个节点的位置，所以在找到该节点后要通过函数来返回该节点，即代码中的 newHead;
3. 反转的操作：L->next->next = L, 这里说明一下：L->next 是下一个指针，而L->next->next 是下一个指针的指向，所以让下一个指针的指向来指向当前指针，从而实现反转。
4. 最后还要令L->next = NULL, 即切断原来正向的指向。
5. 空间复杂度为O(n), 时间复杂度为O(n)

代码如下：

Linklist translateLinklist(Linklist& L)
{
	if (L == NULL || L->next == NULL)
	{
		return L;
	}
	else
	{
		Linklist newHead = digui(L->next);
		L->next->next = L;
		L->next = NULL;
		return newHead;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

最后个人建议熟练掌握头插法、三指针法、递归法，而通过栈来实现的方法了解即可。而递归法最好用于没有头节点的单链表。而头插法和三指针法在任何情况的单链表中均可使用。

本人学艺不精，如有错漏，欢迎指出！