单链表(原地)逆置

单链表实现逆置

从头遍历链表，使每一个结点都指向该结点的上一个节点。最后再处理头结点与为结点即可。

三个指针

对于一个单链表来说，我们不可能从一个结点(Node *i )找到它的上一个节点，所以我们需要额外定义一个指针(Node *s )指向该结点的上一个结点。此外在改变当前结点next指针的指向时会断开与下一结点的连接，所以我们还需要一个指针(Node *t )指向当前结点的下一个结点。

如图所示：

i 指向当前结点，改变当前结点next 指向，同时自动与其后续结点断开；

s 初始为空，代表尾结点指向NULL，随着i 的移动，s 指向新链表的头；

t 指向 i 的下一个结点，以便在单链表断开的情况下还能继续遍历链表。

代码如下：

//单链表逆置 
void Reverse(LNode* List)
{
	LNode* s = nullptr;//空指针	//开始时为空指针，循环时成为新链表的头(类似头插)
	LNode* i = nullptr;			//遍历链表，改变指针(next)指向
	LNode* t = List->next;		//保留断开处的链表
	
	while (t != nullptr)
	{
		i = t;
		t = t->next;	//保存断开处的地址

		i->next = s;	//改变当前结点指向
		s = i;
	}
	List->next = s;    //头结点
}