题解 | #牛群的重新排列#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察的是链表的反转操作，需要注意链表节点的连接和指针的移动。

题目解答方法的文字分析

我们可以使用链表反转的经典思想来解决这个问题。首先，我们需要找到需要反转的部分的前一个节点 prev_left 和后一个节点 next_right。然后，反转从 left 到 right 的节点，并更新相应的连接关系。

具体步骤如下：

1. 初始化一个虚拟头节点 dummy，并将其连接到链表的头节点 head。
2. 创建一个指针 prev，初始时指向虚拟头节点 dummy，用于找到需要反转部分的前一个节点 prev_left。
3. 使用循环将指针 prev 移动到需要反转部分的前一个节点 prev_left。
4. 创建两个指针 left_node 和 right_node，分别指向需要反转部分的第一个节点和最后一个节点。
5. 创建一个指针 next_right，初始时指向需要反转部分的后一个节点，用于后续连接。
6. 使用循环将指针 right_node 移动到需要反转部分的最后一个节点，并同时更新指针 next_right。
7. 反转从 left_node 到 right_node 的节点，并同时更新指针 prev_left 和指针 left_node。
8. 最后，将指针 prev_left 连接到反转后的链表的头节点 right_node，将指针 left_node 连接到指针 next_right。
9. 返回虚拟头节点的下一个节点 dummy->next，即为反转后的链表。

本题解析所用的编程语言

C++

完整且正确的编程代码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy = new ListNode(-1); // 创建一个虚拟头节点
        dummy->next = head; // 将虚拟头节点连接到原链表头部
        ListNode* prev = dummy; // prev 指针，用于定位需要反转部分的前一个节点
        ListNode* prev_left = nullptr; // 需要反转部分的前一个节点
        ListNode* left_node = nullptr; // 需要反转部分的第一个节点
        ListNode* right_node = nullptr; // 需要反转部分的最后一个节点
        ListNode* next_right = nullptr; // 需要反转部分的后一个节点
        
        // 找到需要反转部分的前一个节点 prev_left
        for (int i = 1; i < left; ++i) {
            prev = prev->next;
        }
        prev_left = prev;
        left_node = prev_left->next;
        
        // 找到需要反转部分的最后一个节点 right_node，并更新 next_right
        right_node = left_node;
        for (int i = left; i < right; ++i) {
            right_node = right_node->next;
        }
        next_right = right_node->next;
        
        // 反转从 left_node 到 right_node 的节点
        ListNode* prev_node = nullptr;
        ListNode* curr_node = left_node;
        while (curr_node != next_right) {
            ListNode* temp = curr_node->next;
            curr_node->next = prev_node;
            prev_node = curr_node;
            curr_node = temp;
        }
        
        // 连接反转后的链表部分
        prev_left->next = right_node;
        left_node->next = next_right;
        
        return dummy->next; // 返回新链表的头节点
    }
};

这个代码使用链表反转的思想，通过找到需要反转部分的前一个节点 prev_left 和后一个节点 next_right，然后反转从 left 到 right 的节点。最后，更新连接关系，得到反转后的链表。

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！