【算法】链表：206.反转链表（easy）

系列专栏

《分治》

《模拟》

《Linux》

1、题目链接

2、题目介绍

3、解法（快慢指针）

解题步骤：

关键点：

复杂度分析：

4、代码

1、题目链接

206. 反转链表 - 力扣（LeetCode）

2、题目介绍

3、解法（快慢指针）

这里采用的就是三个指针（或者可以说是两个指针加一个临时变量）的方法来实现链表的反转。

解题步骤：

边界条件处理：
首先检查输入的头节点head是否为nullptr。如果是，直接返回nullptr，因为空链表反转后仍然是空链表。
初始化指针：
cur指针初始化为nullptr，它将会指向反转后的链表的当前节点。在反转过程中，cur会逐渐成为反转后链表的头节点。
NEXT指针初始化为head，它指向当前正在处理的节点。
tmp指针用于临时存储NEXT->next的值，以便在反转NEXT节点的指向后，能够继续遍历原链表。
迭代反转链表：
使用一个while循环，条件是NEXT不为nullptr，表示还有节点需要处理。
在每次循环中，首先用tmp保存NEXT->next的值，即当前节点的下一个节点。
然后将NEXT->next指向cur，完成当前节点的反转。
更新cur和NEXT的值，cur指向NEXT（现在已反转），NEXT指向tmp（即原来的下一个节点）。
返回结果：
当NEXT为nullptr时，循环结束，此时cur指向反转后的链表的头节点。
返回cur即可。

关键点：

指针的更新顺序：先改变当前节点的next指向，再移动指针。
防止链表断裂：使用tmp临时变量保存未处理的链表部分，确保在反转当前节点后，仍然可以访问到剩余链表。
理解指针的作用：cur是反转后链表的当前节点，NEXT是当前正在处理的节点，tmp是临时存储的下一个节点。

复杂度分析：

时间复杂度：O(n)，其中n是链表的长度。因为需要遍历整个链表。
空间复杂度：O(1)。只使用了常数个额外变量，没有使用与链表长度相关的额外空间。

4、代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if (head == nullptr)return head;//快慢双指针//直接一个一个结点的反转ListNode* cur = NULL, *NEXT = head;while (NEXT != NULL){ListNode* tmp = NEXT->next;//tmp临时指针，存放未被反转的链表，防止丢失NEXT->next = cur;cur = NEXT;NEXT = tmp;}return cur;}};