单链表逆置之两种算法的比较

一、第一种算法
1、思路

• 定义两个指针P、Q，P指向链表的头结点，Q指向链表的最后面，也就是len的位置。
• 每当P每次向后移动一个位置，Q就回退，也就是len的位置。P每次向后移动两个位置，Q就回退到len-1的位置。
• 当 P移动到len/2的位置就相当于链表中的元素全部都遍历完，接下来将对称点作交换就可以。

2、代码实现如下：

void Reverse (PList pl)
{
	int len = getLength(pl) ;
	Node* pfront= pl;
	Node* ptail = pl;
	for(inti=O;i<len/2;i++)//交换的次数
	{
		pfront = pl;
		for(int j = 0;j < i+1; j++)//控制front的位置
		{
		pfront = pfront->next;
		}
		ptail = pl;
		for(int k = 0; k < len-i;k++)//ptail走到len-i的位置
		{
		ptail = ptail->next;
		}
		ElemType tmp = pfront ->data;
		pfront->data = ptail->data;
		ptail->data = tmp;
	}
}

3、画图分析


通过分析，我们发现此链表的复杂度为：O（n^2）。此算法的时间复杂度较大。
二、第二种算法
1、思路

• 定义一个指针pcur指向第一个数据结点，然后将头结点断开，形成一个新的空链表。
• 这时候整个单链表被分为两个部分：左边是一个空链表，右边是结点的集合
• 把右边的结点集合的中的结点依次头插到左边的空链表中

2、代码实现

void Reverse (PList pl)
{
	Node* pCur = pl->next;
	Node* pNext = NULL;
	pl->next = NULL;
	while(pCur != NULL)
	{
		pNext = pCur- >next;
    	pCur- >next = p1->next;
   	 	pl->Next = pCur;
   	 	pCur = pNext;
    }
}

3、画图表示

剩下结点的头插类似
这个代码最优，是单链表逆置的最佳写法。
以上便是单链表逆置的两种算法的比较。