初夏小谈：反转单链表（头插法、三指针法）

神奇的链子又来了。昨天对链表进行了基本的增/删/查/改操作，今天来一些链表更进阶的一些执行方法之反转链表。

第一种方法：熟悉的头插法

定义一个新的头指针 ---> 直接把结点依次摘下来 ---> 向新定义的头指针上进行头插。

至于为什么要头插呢？

链表头插就会把原来的结点顺序进行逆序。这就是本方法的最重要的原因。

OK代码如下：

//1.反转链表
//1.1引入一个头指针，进行头插的办法 *****
void ReversalLinkList_TouCha(LinkList* first)
{
	assert(first);
	LinkListNode* ptr = first->head;
	LinkListNode* ptrs;//标记移动结点的下一个结点
	LinkList* Two = (LinkList*)malloc(sizeof(LinkList));
	InitLinkList(Two);
	while (ptr != NULL)
	{
		ptrs = ptr->next;
		if (Two->head != NULL)
		{
			ptr->next = Two->head;
			Two->head =ptr;
		}
		else
		{
			Two->head = ptr;
			ptr->next = NULL;
		}
		ptr = ptrs;
	}
	first->head = Two->head;
}

第二种方法就是三指针法：

所谓三指针法：就是用三个指针依次去指向链表的前三个结点（注意只要有两个及两个以上结点就可以使用），要对没有结点和只有一个节点另外进行判定及相应的处理。接下来就是交换前两个结点，之后把三个指针依次向后移动。直到只有一个结点停止。

为什么会用三指针？

这是因为对该链表进行逆转时，是直接在该链表上进行修改，单链表我们可以很容易想到一个指针是完成不了的，因为他只能找到下一个结点，而对前面结点却束手无策，所以引入第二个指针标记前一个结点，就可以进行交换，但只用两个，那么就会存在一个问题。交换的结点的后一个结点将无法找到。因为它的前一个结点已经变成了交换的结点的第一个。所以必须引用第三个指针来标记交换的结点的后一个结点。

OK代码如下：

//1.2引入三个指针，改变指向的办法
void ReversalLinkList_ThreePoint(LinkList* first)
{
	assert(first);
	LinkListNode* ptr0;
	LinkListNode* ptr1;
	LinkListNode* ptr2;
	LinkListNode* ptr = first->head;
	if ((first->head == NULL) || (ptr->next == NULL))
	{
		return;
	}

	ptr0 = ptr;
	ptr1 = ptr->next;
	ptr2 = ptr->next->next;
	int i = 0;
	while (ptr1 != NULL)
	{
		if (i==0)
		{
			i++;
			ptr0->next = NULL;
		}
		ptr1->next = ptr0;
		first->head = ptr1;
		//移动指针
		ptr0 = ptr1;
		ptr1 = ptr2;
		if (ptr1 != NULL)
		{
			ptr2 = ptr2->next;
		}

	}
}

两次的运行结果：

6 5 4 3 2 1  //原链表
1 2 3 4 5 6  //第一种方法
6 5 4 3 2 1  //第二种方法
请按任意键继续. . .

                                                                                                                                                                          珍&源码