反转单链表的两种最简方法，时间复杂度O(n)，空间复杂度O(1)（C语言）_反转链表 复杂度

我用的是带有头结点的单链表作为演示。

方法一：先看图

第一步：段链，在图示位置将链表分成两个，用指针P作为第二段链表表头，并将1中指针域next制空（可以创建临时指针R进入1中）。

第二步：在图示位置依次执行插入操作(头插法)

第三步：进入循环，PQR三指针如影随形，Q是P的影子，R是Q的影子 

代码如下：

int Reverse_lian(Link L) {
	Link P=L;
	P = P->next;
	Link R = P;
	P = P->next;
	R->next = NULL;
	Link Q = L;
	while (P) {
		L->next = P;
		Q = P;
		P = P->next;
		Q->next = R;
		R = Q;
	}
	return OK;
}

方法一的优点是简单易懂，好理解缺点是需要单独处理一下1所在区域，略显繁琐

方法二：

思想和方法一相同，不过法二直接在head指针和1之间断开，借助head指针的next域作为中间量直接进行插入操作，无需单独处理1

代码如下：

int Reverse_lian_s(Link L) {
	Link P=L->next;
	L->next = NULL;
	Link Q = P;
	while (P)
	{
		P = P->next;
		Q->next = L->next;
		L->next = Q;
		Q = P;
	}
	return OK;
}

优点代码量少，简洁高效，缺点不好想