11. 断藕重连术 - 反转链表（迭代与递归）

哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的藕断湖，湖面上漂浮着一串串断裂的莲藕，每段莲藕上都刻着数字。湖中央有一座巨大的石碑，上面刻着一行文字：“欲破此湖，需以断藕重连术，反转链表，迭代与递归并用。”

哪吒定睛一看，石碑上还有一行小字：“链表1 -> 2 -> 3 -> 4反转后为4 -> 3 -> 2 -> 1。”哪吒心中一动，他知道这是一道关于反转链表的难题，需要将链表中的节点顺序完全反转。

暴力解法：断藕重连术的初次尝试

哪吒心想：“要反转链表，我可以逐个节点遍历，将每个节点的指针反转。”他催动断藕重连术，从链表的头节点开始，逐个节点遍历，将每个节点的指针指向前一个节点。

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;  // 如果链表为空或只有一个节点，直接返回
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;  // 保存下一个节点
        curr->next = prev;            // 反转当前节点的指针
        prev = curr;                  // 更新prev和curr
        curr = next;
    }
    return prev;  // 返回新的头节点
}

哪吒成功地反转了链表，但断藕重连术的光芒却黯淡了下来。他意识到，这种方法虽然可行，但效率较低，尤其是当链表很长时，灵力消耗较大。

C++语法点：链表操作

在C++中，链表是处理动态数据结构的常用工具。以下是一些重要特性：

• 链表节点：
  • 使用ListNode结构体表示链表节点，包含val（节点值）和next（指向下一个节点的指针）。
  • 常用操作：
    • ListNode* head：表示链表的头节点。
    • node->next：访问节点的下一个节点。
• 链表反转：
  • 通过逐个节点遍历，将每个节点的指针指向前一个节点。

高阶优化：递归反转的智慧

哪吒元神中突然浮现金色铭文——「断藕重连，递归反转显神通」。他意识到，可以通过递归的方式，从链表的尾部开始反转，逐步回溯到头部，从而实现链表的反转。

哪吒决定使用递归方法，从链表的头节点开始，逐层递归到链表的尾部，然后逐层回溯，将每个节点的指针指向前一个节点。

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;  // 如果链表为空或只有一个节点，直接返回
    ListNode* newHead = reverseList(head->next);  // 递归反转剩余部分
    head->next->next = head;  // 反转当前节点的指针
    head->next = nullptr;     // 将当前节点的next置为nullptr
    return newHead;           // 返回新的头节点
}

复杂度分析：灵力消耗评估

• 时间复杂度：O(n)，因为需要逐个节点遍历链表。
• 空间复杂度：O(1)（迭代法），O(n)（递归法，递归栈空间）。

哪吒使用优化后的代码，断藕重连术的灵力消耗大幅减少，成功破解了藕断湖的难题。

变式训练：阵法变形的应对

1. 链表为空或只有一个节点：如[]或[1]，直接返回原链表。
2. 链表很长：如长度为1000的链表，验证算法的效率。
3. 链表中包含重复值：如[1, 2, 2, 3]，验证算法的正确性。
4. 链表为环形链表：如1 -> 2 -> 3 -> 1，验证算法的鲁棒性。

哪吒通过这些变式训练，进一步巩固了对链表反转的理解。

太乙口诀：修炼的智慧

断藕重连，递归反转显神通。
迭代逐节点，递归逐层回溯，链表反转成。

口诀解释：

• 断藕重连：象征链表反转的智慧，通过断藕重连术将链表反转。
• 递归反转显神通：通过递归的方式，从链表尾部开始反转，逐步回溯到头部。
• 迭代逐节点：使用迭代法逐个节点反转，适用于空间敏感的场景。
• 递归逐层回溯：使用递归法逐层反转，代码简洁，但需要注意递归栈空间。
• 链表反转成：最终完成链表的反转操作，达到预期效果。

文章总结

在这篇文章中，我们跟随小哪吒学习了如何使用迭代和递归方法解决链表反转的问题。通过暴力解法的尝试，哪吒意识到逐个节点反转虽然简单，但效率较低。在太乙真人的指引下，他领悟了递归反转的精髓，通过从链表尾部开始逐层回溯，大大减少了灵力消耗。我们还详细介绍了C++中链表操作的基本方法，包括节点遍历和指针反转。通过这次修炼，哪吒不仅提升了算法能力，还对链表操作有了更深刻的理解。