网站开发行业代码,太原自助建站系统,做网站建设的前景,巩义网络推广给你单链表的头指针 head 和两个整数 left 和 right #xff0c;其中 left right 。请你反转从位置 left 到位置 right 的链表节点#xff0c;返回 反转后的链表 。
class ListNode {
public:int val;ListNode* next;ListNode(int _val) {val _val;next nullptr;}
};…给你单链表的头指针 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 指针所指向的节点就是反转后的链表头节点整个区间的节点也实现了反转。
