LeetCode 24反转链表

单链表反转：详细解析与代码实现

在数据结构的学习过程中，链表是一个非常重要且有趣的部分，而单链表的反转操作更是常考的基础知识点。今天就来和大家详细讲讲如何实现单链表的反转，并通过代码示例来加深理解呀。

题目

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

思路分析

要反转单链表，核心思路就是改变链表节点中指针的指向方向。我们可以想象成把原来依次相连的节点，逐个 “掉头”，让它们按照相反的顺序重新连接起来。

为了实现这个过程，我们采用迭代的方法，借助几个指针来帮忙操作：

1. prev 指针：这个指针一开始初始化为 NULL，它的作用是始终指向当前节点的前一个节点。在反转的过程中，它相当于一个 “锚点”，让当前节点能够指向它，从而改变链表的连接方向。
2. curr 指针：初始化为链表的头节点 head，它代表着我们当前正在处理的节点。在每一轮循环中，我们都会对这个节点进行操作，改变它的 next 指针指向。
3. nextTemp 指针：它用于临时保存当前节点的下一个节点。为什么要这么做呢？因为一旦我们改变了当前节点 curr 的 next 指针指向（让它指向 prev），如果不提前保存下一个节点的信息，那就会丢失后续链表的连接情况，导致链表断裂呀。

整个反转过程就是通过不断地循环，在每一轮循环中完成以下几个关键步骤：

• 首先，使用 nextTemp 保存 curr 节点的下一个节点，也就是执行 nextTemp = curr->next; 这一步，确保后续链表不会丢失。
• 接着，把当前节点 curr 的 next 指针指向它前面的节点 prev，即 curr->next = prev;，这一步就是真正改变链表连接方向，实现 “反转” 的关键操作哦。
• 然后，更新 prev 指针，让它指向当前节点 curr，执行 prev = curr;，为下一轮循环做准备，因为下一轮循环中，当前节点就变成了之前保存的 nextTemp 所指向的节点了，而此时的 prev 就要相应跟上呀。
• 最后，更新 curr 指针，让它指向之前保存的下一个节点 nextTemp，也就是 curr = nextTemp;，这样就可以进入下一轮循环，继续处理链表中的下一个节点啦。

当循环结束，也就是 curr 遍历到原链表的末尾（即 curr 变为 NULL）时，prev 指针就正好指向了反转后链表的头节点啦，我们最后返回这个 prev 就大功告成咯。

代码实现

下面就是使用 C 语言实现单链表反转的完整代码啦：

#include <stdio.h>
#include <stdlib.h>// 单链表节点结构体定义
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode {int val;struct ListNode *next;
};// 创建单链表节点的函数
struct ListNode* createNode(int val) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));if (newNode == NULL) {printf("内存分配失败！\n");return NULL;}newNode->val = val;newNode->next = NULL;return newNode;
}// 向链表末尾插入节点的函数
void insertNode(struct ListNode** head, int val) {struct ListNode* newNode = createNode(val);if (*head == NULL) {*head = newNode;} else {struct ListNode* temp = *head;while (temp->next!= NULL) {temp = temp->next;}temp->next = newNode;}
}// 打印单链表的函数
void printList(struct ListNode* head) {struct ListNode* temp = head;while (temp!= NULL) {printf("%d ", temp->val);temp = temp->next;}printf("\n");
}// 反转单链表的函数
struct ListNode* reverseList(struct ListNode* head) {if (head == NULL) {return head;}struct ListNode *prev = NULL;struct ListNode *curr = head;struct ListNode *nextTemp;while (curr!= NULL) {nextTemp = curr->next;curr->next = prev;prev = curr;curr = nextTemp;}return prev;
}int main() {struct ListNode* head = NULL;// 构建一个简单的单链表，例如1 -> 2 -> 3 -> 4 -> 5insertNode(&head, 1);insertNode(&head, 2);insertNode(&head, 3);insertNode(&head, 4);insertNode(&head, 5);printf("原单链表为: ");printList(head);struct ListNode* reversedHead = reverseList(head);printf("反转后的单链表为: ");printList(reversedHead);return 0;
}