【亡羊补牢】挑战数据结构与算法 第62期 LeetCode 92. 反转链表 II(链表)
发布日期:2021-06-29 14:34:41
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月24日 15时01分08秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
struts2中<s:if>标签的使用
2019-04-29
js 刷新页面window.location.reload();
2019-04-29
【转】EasyUI 验证
2019-04-29
java开发时内存溢出问题
2019-04-29
【easyui】combobox 关于省市联动
2019-04-29
设置csdn皮肤方法,更改自己喜欢的老版皮肤
2019-04-29
Eclipse中无法查看JDK源码,解决方法
2019-04-29
Git操作常用口令
2019-04-29
IDEA去除掉虚线,波浪线,和下划线实线的方法
2019-04-29
MYSQL新特性secure_file_priv 读写文件
2019-04-29
idea中的一些常用快捷键
2019-04-29
最值得拥有的免费Bootstrap后台管理模板
2019-04-29
Django获取请求头信息和返回json数据
2019-04-29
Django项目实战----点击商品分类查询出商品和销量排行
2019-04-29
Django项目实战---搜索引擎Elasticsearch
2019-04-29
Django实战----页面静态化
2019-04-29
Django实战---商城购物车的增删改、显示和合并购物车
2019-04-29
Django项目实战----订单页面的显示和生成订单、提交订单的逻辑
2019-04-29