网站后台更新文章 前台不显示,网站建设 甘肃,wordpress网格布局,网站app软件下载安装目录 题目题解进阶 题目
给你单链表的头指针 head 和两个整数 left 和 right #xff0c;其中 left right 。请你反转从位置 left 到位置 right 的链表节点#xff0c;返回 反转后的链表 。
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], left 2, right 4… 目录 题目题解进阶 题目
给你单链表的头指针 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]
提示链表中节点数目为 n
1 n 500
-500 Node.val 500
1 left right n题解
看到这个题目之后我们第一时间可能想到用ArrayList包过所有的节点然后通过ArrayList的下标更换来实现链表的反转。代码如下
public ListNode reverseBetween1(ListNode head, int left, int right) {ListListNode list new ArrayList();// 遍历链表while (head ! null) {list.add(head);head head.next;}// 交换for (int i left - 1, j right - 1; i j; i, j--) {ListNode temp list.get(i);list.set(i, list.get(j));list.set(j, temp);}// 重新连接for (int i 0; i list.size() - 1; i) {list.get(i).next list.get(i 1);}// 最后一个节点的next置为nulllist.get(list.size() - 1).next null;return list.get(0);
}但这样明眼可见内存和时间都会很不理想首先遍历了三次链表相当于O(3 * head.length), 空间复杂度也非常高。这个时候我们会想到能不能我的ArrayList只存需要反转那一部分呢然后再跟不需要反转的链表合并连接下。
空间利用率提升 public ListNode reverseBetween(ListNode head, int left, int right) {ListNode startHeadPre null; // left 节点的前一个节点ListNode endPre null; // right 节点的后一个节点ListNode pre new ListNode(); // 辅助节点用于遍历链表pre.next head; // 将辅助节点的下一个节点指向原始链表的头节点ListNode realHead pre; // 记录原始链表的头节点ListListNode listNodes new ArrayList(); // 用于存储需要反转的节点int index 0; // 当前遍历的节点索引while (head ! null head.next ! null) {if (index left - 1) {startHeadPre pre; // 记录 left 节点的前一个节点}if (startHeadPre null) {index ;pre head;head head.next;continue;}listNodes.add(head); // 将需要反转的节点加入到 listNodes 中if (index right - 1) {endPre head.next; // 记录 right 节点的后一个节点break;}index;pre head;head head.next;}if (right - 1 index) {listNodes.add(head); // 如果 right 节点是最后一个节点则将其加入到 listNodes 中}ListNode reHead new ListNode(); // 反转后的链表头节点ListNode reHeadTemp reHead; // 用于遍历反转后的链表if (listNodes.size() 0) {reHead.next listNodes.get(listNodes.size() - 1); // 反转后的链表头节点指向 listNodes 的最后一个节点reHeadTemp reHead.next;for (int i listNodes.size() - 2; i 0; i--) {reHeadTemp.next listNodes.get(i); // 逐个将节点加入到反转后的链表中reHeadTemp reHeadTemp.next;}}if (left - 1 0) {realHead.next reHead.next; // 如果 left 节点是原始链表的头节点则更新原始链表的头节点为反转后的链表头节点}if (startHeadPre ! null) {startHeadPre.next reHead.next; // 将 left 节点的前一个节点的 next 指针指向反转后的链表头节点}reHeadTemp.next endPre; // 将反转后的链表尾节点的 next 指针指向 right 节点的后一个节点return realHead.next; // 返回原始链表的头节点
}这段代码实现了将链表中从 left 到 right 区间的节点进行反转。它使用了多个辅助节点和变量来记录反转过程中的节点位置。
通过遍历链表找到 left 节点的前一个节点 startHeadPre 和 right 节点的后一个节点 endPre。同时将需要反转的节点存储在 listNodes 中。
然后创建反转后的链表头节点 reHead并通过遍历 listNodes 将节点逐个加入到反转后的链表中。 最后根据情况更新原始链表的头节点和连接反转后的链表。 这段代码的时间复杂度为 O(n)其中 n 是链表的长度。然而它的实现方式相对复杂且效率较低。可以使用更简单和高效的方法来实现链表反转。 可以看到空间复杂度低了但是代码异常复杂很难理解水平有限。而且时间复杂度和空间复杂度也不是最优能不能使用一趟扫描完成反转
进阶
你可以使用一趟扫描完成反转吗
public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummy new ListNode(); // 创建虚拟头节点dummy.next head; // 将虚拟头节点指向原始链表的头节点ListNode prev dummy; // prev 指针用于定位到 left 的前一个节点// 移动 prev 到 left 的前一个节点for (int i 0; i left - 1; i) {prev prev.next;}ListNode start prev.next; // 记录 left 节点ListNode end start; // 记录 right 节点ListNode curr start.next; // 当前节点// 反转链表节点for (int i left; i right; i) {ListNode next curr.next; // 保存当前节点的下一个节点curr.next prev.next; // 将当前节点的 next 指针指向 prev 的 next 节点prev.next curr; // 将 prev 的 next 指针指向当前节点start.next next; // 将 start 的 next 指针指向 next 节点保持链表连接curr next; // 更新当前节点为下一个节点}return dummy.next; // 返回虚拟头节点的下一个节点即为反转后的链表
} 这段代码实现了将链表中从 left 到 right 区间的节点进行反转。它使用了一个虚拟头节点 dummy并通过 prev 指针定位到 left 的前一个节点。
在反转过程中使用 start 记录 left 节点end 记录 right 节点curr 作为当前节点。通过遍历链表将 curr 节点插入到 prev 节点之后同时更新 start 节点和 curr 节点的位置。
最后返回虚拟头节点的下一个节点即为反转后的链表。
这段代码的时间复杂度为 O(n)其中 n 是链表的长度。
