单链表的逆置

上篇博客讲了单链表以及其各项功能的实现，本篇博客就来谈谈如何将一个单链表逆置。单链表的逆置主要有两种方法，我们结合代码来进行了解。

方法一：翻转单链表中指针的指向

要翻转一个单链表中指针的指向，我们一共需要新建三个指针，其中两个用来进行指针的翻转，第三个用来保存下一个的地址。
1、将n1的初值设为头，n2为n1的next，n3为n2的next，以n2是否为空作为循环判断条件
2、在进入循环前将n1的next置为空，即n1作为尾
3、每次循环的操作为：n2的next置为n1，n1=n2，n2=n3，n3=n3->next
注意：当进行最后两个时，n3为空，那么会出现空指针的访问，因此需要在该语句加判断
完整代码如下：

PlistNode* reverseList1(PlistNode** head)
{
	if ((*head == NULL) || ((*head)->_next == NULL))
		return *head;
	PlistNode* n1 = (*head);
	PlistNode* n2 = (*head)->_next;
	PlistNode* n3 = n2->_next;
	n1->_next = NULL;
	while (n2 != NULL)
	{
		n2->_next = n1;
		n1 = n2;
		n2 = n3;
		if (n3 != NULL)//要考虑最后两个的情况
			n3 = n3->_next;
	}
	return n1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

到这里我们通过翻转指针指向完成了单链表的逆置，这是一种在原本链表上进行修改的行为。

那么可不可以通过新建一个链表来完成逆置单链表的操作呢?当然可以

方法二：开辟新的空间，利用一个临时量遍历原链表，将原链表的每一个值头插到一个新的链表上

完整代码如下：

PlistNode* reverseList(PlistNode** head)
{
	if ((*head) == NULL || (*head)->_next == NULL)
		return (*head);
	PlistNode* cur = *head;
	PlistNode* newhead = GetNode(cur->_date);
	PlistNode* tmp = NULL;
	while (cur->_next != NULL)
	{
		cur = cur->_next;
		tmp = GetNode(cur->_date);
		tmp->_next = newhead;
		newhead = tmp;
	} 
	return newhead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

当我们在思考一个问题的时候，不应该只是单纯的片面的通过最基本的方式去解决，应当拓展思维，用更优化的方式去实现自己的目的，这是程序设计的本质。