【亡羊补牢】挑战数据结构与算法 第62期 LeetCode 92. 反转链表 II(链表)
发布日期:2021-06-29 14:34:41
浏览次数:3
分类:技术文章
本文共 2222 字,大约阅读时间需要 7 分钟。
仰望星空的人,不应该被嘲笑
题目描述
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4输出: 1->4->3->2->5->NULL
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-linked-list-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。解题思路
借助递归
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} head * @param {number} m * @param {number} n * @return {ListNode} */var reverseBetween = function (head, m, n) { let reverse = (pre, cur) => { if (!cur) return pre; let tmp = cur.next; cur.next = pre; return reverse(cur, tmp); } let dummyHead = new ListNode(); dummyHead.next = head; let p = dummyHead; let k = m - 1; // 先找到需要反转链表部分的前驱节点 while (k--) { p = p.next; } // 保存前驱节点 let front = p; // 找到需要反转链表部分的头节点 let frontNode = front.next; k = n - m + 1; // 再找到需要反转链表部分的尾节点 while (k--) { p = p.next; } // 找到需要反转链表部分的尾节点 let endNode = p; // 保存后继节点 let end = endNode.next; // 将后继值为空,开始反转链表 endNode.next = null; front.next = reverse(null, frontNode); // 原本的反转链表部分的头节点现在变成了尾节点,指向原本的后继节点 frontNode.next = end; return dummyHead.next;};
迭代解法
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} head * @param {number} m * @param {number} n * @return {ListNode} */var reverseBetween = function(head, m, n) { let dummyHead = new ListNode(); dummyHead.next = head; let p = dummyHead; let k = m-1; // 先找到需要反转链表部分的前驱节点 while (k--) { p = p.next; } // 保存前驱节点 let front = p; let pre = frontNode = front.next; let cur = pre.next; k = n-m; // 长度为3的链表需要反转2次,那么长度为n的链表需要反转n-1次 while(k--){ let tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } // 将原本前驱节点的next指向当前反转后的链表 front.next = pre; // 原本反转链表的头节点现在变成了尾结点,指向后继节点 frontNode.next = cur; return dummyHead.next;};
最后
文章产出不易,还望各位小伙伴们支持一波!
往期精选:
小伙伴们可以在Issues中提交自己的解题代码,🤝 欢迎Contributing,可打卡刷题,Give a ⭐️ if this project helped you!
,方便小伙伴阅读玩耍~
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/108920381 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月09日 16时27分00秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
基于Java的截图工具
2019-04-29
基于JAVA的停车场管理系统
2019-04-29
基于Java实现的商品推荐系统
2019-04-29
基于SSM的网上购物系统的设计与开发
2019-04-29
基于SSM框架的BS微博系统的设计与实现
2019-04-29
超市订单管理系统
2019-04-29
基于ssm的民宿网站
2019-04-29
基于JavaWeb的物流管理系统的设计与实现
2019-04-29
基于Java的飞机大战游戏的设计与实现论文
2019-04-29
基于java实现的超级马里奥游戏
2019-04-29
ansible自动化运维2: playbook
2019-04-29
keepalived 实现高可用,负载均衡
2019-04-29
linux发送邮件通知
2019-04-29
linux不删除文件:替换rm命令
2019-04-29
Centos6 搭建lnmp环境
2019-04-29
Hbase优化:使用压缩snappy,lz4
2019-04-29
maven 安装第三方jar包到本地仓库
2019-04-29
hbase数据结构模型
2019-04-29
Shell编程:return 返回脚本调用的状态码
2019-04-29
Hbase Shell 调用java代码:通过比较器,强过滤查询
2019-04-29