【C++】每日一题 92 反转链表

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

class ListNode {
public:int val;ListNode* next;ListNode(int _val) {val = _val;next = nullptr;}
};ListNode* reverseBetween(ListNode* head, int left, int right) {if (head == nullptr || left == right) {return head;}ListNode dummy(0);dummy.next = head;ListNode* pre = &dummy;for (int i = 0; i < left - 1; i++) {pre = pre->next;}ListNode* cur = pre->next;for (int i = 0; i < right - left; i++) {ListNode* next = cur->next;cur->next = next->next;next->next = pre->next;pre->next = next;}return dummy.next;
}

先创建一个虚拟头节点 dummy，然后找到需要反转位置的前一个节点 pre。接着进行反转操作，将节点逐个插入到 pre 节点之后，最后返回虚拟头节点的 next 即可得到反转后的链表。

关键反转操作在第二个for循环，（第一个for循环是为了寻找起始操作位置），第二个for循环每次迭代都会将当前节点的后继指针指向前一个节点，从而改变了链表中节点的指向关系，实现了反转效果。

具体解释如下：

在开始循环之前，pre 指针指向要反转区间的前一个节点，cur 指针指向要反转区间的第一个节点，next 指针指向 cur 的下一个节点。
首先，将 cur->next 指向 next->next，即将 cur 节点的后继指针指向 next 节点的后一个节点，断开了 cur 节点与 next 节点的联系。
然后，将 next->next 指向 pre->next，即将 next 节点的后继指针指向 pre 节点的后一个节点，将 next 节点插入到 pre 节点之后。
最后，更新 pre、cur 和 next 指针，使它们分别指向下一个节点，继续进行下一轮反转操作。
通过以上操作，循环不断地将当前节点的后继指针指向前一个节点，实现了链表节点的反转。最终完成循环后，pre 指针所指向的节点就是反转后的链表头节点，整个区间的节点也实现了反转。