LeetCode:92. 反转链表 II
发布日期:2022-09-10 02:16:49
浏览次数:1
分类:技术文章
本文共 1717 字,大约阅读时间需要 5 分钟。
给你单链表的头指针 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
解题思路
1.首先将待反转的子区间进行反转
2.然后把 pre 的 next 指针指向反转以后的链表头节点,把反转以后的链表的尾节点的 next 指针指向 curr 3.最后返回 dummyNode.next(即原先的head,因为head也有可能在反转区间里,所有采用dummyNode虚拟节点)即可,整个过程大致如下图代码
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @param {number} left * @param {number} right * @return {ListNode} */var reverseBetween = function(head, left, right) { // 因为头节点有可能发生变化,使用虚拟头节点可以避免复杂的分类讨论 const dummyNode = new ListNode(-1); dummyNode.next = head; let pre = dummyNode; // 第 1 步:从虚拟头节点走 left - 1 步,来到 left 节点的前一个节点 // 建议写在 for 循环里,语义清晰 for (let i = 0; i < left - 1; i++) { pre = pre.next; } // 第 2 步:从 pre 再走 right - left + 1 步,来到 right 节点 let rightNode = pre; for (let i = 0; i < right - left + 1; i++) { rightNode = rightNode.next; } // 第 3 步:切断出一个子链表(截取链表) let leftNode = pre.next; let curr = rightNode.next; // 注意:切断链接 pre.next = null; rightNode.next = null; // 第 4 步:同第 206 题,反转链表的子区间 reverseLinkedList(leftNode); // 第 5 步:接回到原来的链表中 pre.next = rightNode; leftNode.next = curr; return dummyNode.next;};const reverseLinkedList = (head) => { let pre = null; let cur = head; while (cur) { const next = cur.next; cur.next = pre; pre = cur; cur = next; }}
转载地址:https://blog.csdn.net/Bertil/article/details/123816552 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月29日 12时17分43秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
has been blocked by CORS policy: Response to preflight request doesn‘t pass access control check 报错
2019-05-01
使用aspose.words 18.6实现pdf文档转换
2019-05-01
Java数组详解
2019-05-01
Java面向对象详解
2019-05-01
vs中动态DLL与静态LIB工程中加入版本信息的方法
2019-05-01
大数据分析技术与应用一站式学习(值得收藏)_v20200418
2019-05-01
Qt 在windows下的串口读写
2019-05-01
SpringApplication执行流程
2019-05-01
自定义Starter
2019-05-01
分布式事务原理探究(一)
2019-05-01
spring cloud consul 应用的多实例名的解决
2019-05-01
人工智能为什么这么火?看看安防江湖30年血战就知道了
2019-05-01
“前端智能为安防产生新的数据价值”
2019-05-01
高斯混合模型
2019-05-01
(8)CMake入门笔记--CMake语法
2019-05-01
3D点云图实验
2019-05-01
头文件中 #ifndef---#define---#endif的作用
2019-05-01
分析Linux内核启动过程:从start_kernel到init
2019-05-01
系统调用过程的理解
2019-05-01