系列专栏

《分治》 

《模拟》

《Linux》

---

目录

1、题目链接

2、题目介绍

3、解法（快慢指针）

解题步骤：

关键点：

复杂度分析：

4、代码 

---

1、题目链接

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

2、题目介绍

3、解法（快慢指针）

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

解题步骤：

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

};

---

💗感谢阅读！💗

---