题解 | #反转链表#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) {
        // write code here
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* next = head->next;
        while (cur != nullptr) {
            cur->next = pre;
            pre = cur;
            cur = next;
            next = cur->next;

        }
        return pre;

    }
};

翻转单链表是一道常见的算法题目，主要考察对链表结构的理解和操作能力。以下是翻转单链表的基本思路：

1. 初始化三个指针：分别是 prev、curr 和 next。在翻转开始前，prev 指向 null，curr 指向链表的头节点。
2. 遍历链表：遍历整个链表，对每个节点进行翻转操作。在遍历的过程中，curr 指向当前正在处理的节点。
3. 翻转操作：首先，将 curr 的 next 指针存储在 next 中，这样就不会丢失原链表的其余部分。接着，改变 curr 的 next 指针，使其指向 prev。这是实际的翻转操作。最后，移动 prev 和 curr 指针，前进到下一个节点。具体来说，prev 移动到 curr 的位置，而 curr 移动到 next 的位置。
4. 继续遍历直到链表末尾：重复步骤 3，直到 curr 变为 null，这表示已到达链表的末尾。
5. 返回新的头节点：当遍历完成时，prev 指针将指向新的头节点，因为原链表的末尾现在成为了翻转后的头部。

这个过程中，重要的是要保持对所有节点的控制，确保在翻转节点的链接时不会丢失对链表的访问。简单的翻转操作只需要修改节点的 next 指针，而不需要创建新的节点，因此这个算法的空间复杂度是 O(1)，时间复杂度是 O(n)，其中 n 是链表的长度。