文章目录
- 前言
- 基本思路
- 代码总览
- 举例分析
前言
在单向链表的创建与遍历中，我们知道了如何创建并且遍历单向链表。那么，如果要将一个链表进行逆转（将链表的第一个元素转为最后一个元素，第二个元素转为倒数第二个元素，以此类推），又该如何实现呢？
说到这里，有些博友可能会想到：创建一个临时变量temp，并创建两个指针P1，P2，P1指向链表开头，P2指向链表末尾，然后通过temp变量将P1和P2指向的结点的数据域进行交换，然后将P1向后移，P2向前移，继续交换数据域，直到全部交换。这样必然是可行的，但我们这次的要求是：不创建临时变量，做到链表逆转。
接下来我们看看如何在不创建临时变量的情况下将链表逆转。
基本思路
单向链表的指针指向是从头开始，一直指到尾。我们如果想要将一个单向链表进行逆转，只需在遍历链表的时候改变每个结点之间指针的指向即可，即让单向链表的指针指向变成从尾指到头，最后将逆转后新链表的头指针返回即可。
在遍历链表的时候，我们是从头开始遍历，在遍历的过程中需要时刻“记住”下一个结点的位置，否则当我们将某个结点的指针方向改变后就无法找到下一个结点，所以我们可以用一个指针先保存下一个结点的地址，然后再改变该结点的指针方向，这样便能找到下一个结点位置了。
代码总览
typedef int ElementType;//定义数据类型，可根据需要进行其他类型定义
//链表结点定义
typedef struct ListNode
{
ElementType Data;//数据域，存储数据
struct ListNode* Next;//指针域，存储下一个结点的地址
}Node, *PNode;
PNode ReverseList(PNode List)
{
PNode Old_head = List;//第一个含有数据的结点地址
PNode New_head = NULL;
while (Old_head != NULL)
{
PNode Temp = Old_head->Next;//Temp存储下一个结点的地址
Old_head->Next = New_head;//改变指针指向
New_head = Old_head;//New_head后移
Old_head = Temp;//Old_head读取下一个结点的地址
}
return New_head;//返回新链表的第一个结点位置
} 举例分析
仅仅看代码可能并不能理解代码的含义，这时我们就得举个例子，通过画图来进一步了解代码的含义。
例如，某一单向链表的数据为：2，3，4，5。我们要对该链表进行逆序，代码执行的过程如下，其中一个长方块代表一个结点，长方块左半部分是数据域，右半部分是指针域，红色线代表当前循环所进行的操作，蓝色番号表示执行的先后顺序。
循环还未进行时，布局如下：
当循环进行一次后，布局变为：
继续循环：
再循环：
再来一次循环：
这时，因为Old_head为空指针，跳出循环，结果就是这样的：
当然，这样看着不怎么顺眼，我们可以重新排一下位置：