网站app建设图片,网站制作要求,网站报价方案 模板,乐清网站推广公司#x1f4dd;个人主页#xff1a;五敷有你 #x1f525;系列专栏#xff1a;算法分析与设计
⛺️稳中求进#xff0c;晒太阳 题目
给你单链表的头指针 head 和两个整数 left 和 right #xff0c;其中 left right 。请你反转从位置 left 到位置 right 的链表… 个人主页五敷有你 系列专栏算法分析与设计
⛺️稳中求进晒太阳 题目
给你单链表的头指针 head 和两个整数 left 和 right 其中 left right 。请你反转从位置 left 到位置 right 的链表节点返回 反转后的链表 。
示例
示例 1 输入head [1,2,3,4,5], left 2, right 4
输出[1,4,3,2,5]示例 2
输入head [5], left 1, right 1
输出[5]
思路虚拟头节点
创建一个虚拟节点 dummy并将其 next 指向 head这样做是为了简化边界情况的处理。找到左边界的前一个节点 prev。遍历链表移动 prev 指针到第 left - 1 个节点处。从 prev 开始遍历链表直到达到右边界的位置 right。在遍历过程中依次将当前节点的 next 指针指向其后继节点的后继节点即跳过当前节点的后继节点然后将后继节点连接到 prev 节点后面。重复这一过程直到完成 left 到 right 区间的节点逆序。返回虚拟节点 dummy 的 next 指针即为反转后的链表头节点。
代码实现
class ListNode {int val;ListNode next;ListNode(int x) { val x; }
}public class ReverseLinkedListBetween {public ListNode reverseBetween(ListNode head, int left, int right) {if (head null || left right) {return head;}// 使用虚拟节点来简化操作ListNode dummy new ListNode(-1);dummy.next head;// 找到左边界的前一个节点ListNode prevLeft dummy;for (int i 1; i left; i) {prevLeft prevLeft.next;}// 开始头插法反转ListNode current prevLeft.next;for (int i left; i right; i) {ListNode next current.next;current.next next.next;next.next prevLeft.next;prevLeft.next next;}return dummy.next;}
}运行结果
