链表反转的原理和方法
链表是一种常见的数据结构，它由一系列的节点组成，每个节点包含一个数据域和一个指针域。链表的特点是可以灵活地增加或删除节点，而不需要连续的内存空间。链表有单向链表、双向链表、循环链表等不同类型。
链表反转是指将一个链表中的节点顺序颠倒过来，使得原来的头节点变成尾节点，原来的尾节点变成头节点，以及原来的每个节点都指向它的前一个节点。例如，如图 1 所示：
经过反转后，得到的新链表如图 2 所示：
通过对比图 1 和 图 2 中的链表不难得知，所谓反转链表，就是将链表整体“反过来”，将头变成尾、尾变成头。
那么如何实现这样一个操作呢？常用的实现方案有以下几种：
- 迭代反转法
- 递归反转法
- 就地逆置法
- 头插法
下面我们分别介绍这些方法，并给出相应的示例代码和注释。
1. 迭代反转法
该算法的实现思想非常直接，就是从当前链表的首元节点开始，一直遍历至链表的最后一个节点，这期间会逐个改变所遍历到的节点的指针域，另其指向前一个节点。
具体地说，我们需要借助三个指针来完成这个操作：
-
prev：指向当前遍历到的节点之前（左边）已经被反转过了部分子列表中最后（右边）一个元素。 -
cur：指向当前遍历到并且正在被处理（即要被翻转）部分子列表中第一个（左边）元素。 -
next：用于保存当前遍历到并且正在被处理部分子列表中第二个（右边）元素。
初始时，prev 指向空（因为还没有任何元素被翻转），cur 指向首元结点（因为首元结点是第一个要被翻转），next 指向第二个结点（因为要保存下一个要被翻转）。如图 3 所示：
然后我们开始迭代地执行以下步骤¹：
- 将
cur->next指针改为指向prev - 将
prev指针移动到cur - 将
cur指针移动到next - 将
next指针到cur->next
重复这些步骤，直到 cur 指向空（即链表的最后一个节点的后一个位置），此时 prev 指向链表的最后一个节点（即反转后的首元节点），如图 4 所示：
因此，我们只需要返回 prev 即可得到反转后的链表。
用 C 语言实现该算法的示例代码如下¹：
// 定义链表结点结构体
struct ListNode {
int val; // 数据域
struct ListNode *next; // 指针域
};
// 迭代反转法
struct ListNode* reverseList(struct ListNode* head) {
// 定义三个指针 prev、cur、next
struct ListNode *prev = NULL;
struct ListNode *cur = head;
struct ListNode *next = NULL;
// 遍历链表，逐个改变指针域的指向
while (cur != NULL) {
next = cur->next; // 保存下一个要被处理的节点
cur->next = prev; // 将当前节点指向前一个节点
prev = cur; // 将前一个节点移动到当前节点
cur = next; // 将当前节点移动到下一个要被处理的节点
}
return prev; // 返回反转后的链表头结点
}
2. 递归反转法
该算法和迭代反转法的思想恰好相反，它是从链表的尾节点开始，依次向前遍历，遍历过程中依次改变各节点的指针域，使其指向前一个节点。
具体地说，我们需要借助两个指针来完成这个操作：
-
head：指向当前正在被处理（即要被翻转）部分子列表中第一个（左边）元素。 -
new_head：用于保存已经被处理过了部分子列表中第一个（左边）元素。
初始时，head 指向首元结点（因为首元结点是第一个要被翻转），new_head 指向空（因为还没有任何元素被翻转）。如图 5 所示：
然后我们开始递归地执行以下步骤：
- 如果
head或者head->next是空，则返回head - 否则，将
head->next节点作为新的head继续递归调用本函数，并将结果赋值给new_head - 将原来的
head->next->next指针改为指向原来的head - 将原来的
head->next指针改为指向空
重复这些步骤，直到递归结束，此时返回值就是反转后的链表头结点。如图 6 所示：
用 C 语言实现该算法的示例代码如下
// 定义链表结点结构体
struct ListNode {
int val; // 数据域
struct ListNode *next; // 指针域
};
// 递归反转法
struct ListNode* reverseList(struct ListNode* head) {
// 定义两个指针 head 和 new_head
struct ListNode *new_head = NULL;
// 如果 head 或者 head->next 是空，则返回 head
if (head == NULL || head->next == NULL) {
return head;
}
// 否则，将 head->next 节点作为新的 head 继续递归调用本函数，并将结果赋值给 new_head
new_head = reverseList(head->next);
// 将原来的 head->next->next 指针改为指向原来的 head
head->next->next = head;
// 将原来的 head->next 指针改为指向空
head->next = NULL;
return new_head; // 返回反转后的链表头结点
}
3. 头插法
该算法是利用一个新建的空链表（带头节点或不带头节点均可），遍历原链表，将每个遍历到的节点插入到新链表的首部，从而实现链表反转。
具体地说，我们需要借助三个指针来完成这个操作：
-
head：指向原链表中当前正在被处理（即要被翻转）部分子列表中第一个（左边）元素。 -
cur：指向原链表中当前正在被处理（即要被翻转）部分子列表中最后一个（右边）元素。 -
new_head：指向新建空链表中第一个（左边）元素。
初始时，head 指向首元结点（因为首元结点是第一个要被翻转），cur 指向空（因为还没有任何元素被翻转），new_head 指向新建空链表中唯一的头节点。如图 7 所示：
然后我们开始迭代地执行以下步骤
- 如果
head是空，则返回new_head - 否则，将
head节点从原链表中断开，并保存其下一个节点到cur - 将
head节点插入到新链表的首部，即将其放在new_head的后面，并更新new_head - 将
cur节点作为新的head
重复这些步骤，直到迭代结束，此时返回值就是反转后的链表头结点。如图 8 所示：
用 C 语言实现该算法的示例代码如下
// 头插法
struct ListNode* reverseList(struct ListNode* head) {
// 定义一个新建的空链表 new_head
struct ListNode *new_head = NULL;
// 定义一个指针 cur 用来保存 head 的下一个节点
struct ListNode *cur = NULL;
// 迭代地执行以下步骤
while (head != NULL) {
// 将 head 节点从原链表中断开，并保存其下一个节点到 cur
cur = head->next;
// 将 head 节点插入到新链表的首部，即将其放在 new_head 的后面，并更新 new_head
head->next = new_head;
new_head = head;
// 将 cur 节点作为新的 head
head = cur;
}
return new_head; // 返回反转后的链表头结点
}
这样就完成了头插法反转链表
