写点什么

LeetCode 题解:92. 反转链表 II,迭代,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 12 月 23 日
LeetCode题解:92. 反转链表 II,迭代,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/reverse-linked-list-ii/



解题思路:



  1. 参考了官方题解中的方法二: 迭代链接反转,你可以其中的图片理解。

  2. 如果你对反转链表不熟悉,可以先尝试206. 反转链表

  3. 使用prev和curr指针进行链表反转,先将两个指针移动到m-1和m位置。

  4. 在进行反转的时候,链表会被分成三段,第一段和第三段不变,中间的第二段被反转。

  5. 链表完成反转之后,m-1节点即为第一段链表的尾结点。原来的m节点从第二段的头结点,变成了第二段链表的尾结点。curr指针会移动到第三段链表的头结点,如果第三段链表不存在,curr就为null

  6. 最后将三段链表连接起来即可。需要注意的是,如果m为1,也就是第一段链表不存在的时候,链表的头结点其实已经变成了第二段链表的头结点,因此需要重新设置一次头结点。



/**
* @param {ListNode} head
* @param {number} m
* @param {number} n
* @return {ListNode}
*/
var reverseBetween = function(head, m, n) {
let prev = null // 用于反转的前置指针
let curr = head // 用于反转的当前指针98j9
// 将prev和head都移动m-1次,prev在m-1位置,head在m位置
while (m > 1) {
prev = curr
curr = curr.next
// 每次循环将m减1,控制移动次数
m--
// 移动指针的同时,需要减少n的数量,完成移动后剩下的n次,即为反转链表的次数
n--
}
let prevListTail = prev // prev即为链表反转后,前半段的尾指针
let reversedListTail = curr // curr即为链表反转后,反转部分的尾指针
// 将链表反转n次
while (n > 0) {
// 反转链表节点的通用方法
let next = curr.next
curr.next = prev
prev = curr
curr = next
// 每次循环将n减1,控制移动次数
n--
}
// 如果prevListTail不为空,即为链表中间的一段进行了反转,需要将前半段与反转后的链表头指针连接起来
if (prevListTail) {
// 链表反转后,prev的位置即为反转部分的头指针
prevListTail.next = prev
} else {
// 链表未空,表示链表从头开始反转,反转后的prev即为新链表的头,因此需要重新设置链表的头指针
head = prev
}
// 链表反转后,反转部分原来的头,变成了尾部,而curr已加移出了链表,成为了最后一段链表的头指针
// 因此需要将反转部分的尾指针与最后一段的头指针连接起来,组成新链表
reversedListTail.next = curr
return head
};



发布于: 2020 年 12 月 23 日阅读数: 10
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:92. 反转链表 II,迭代,JavaScript,详细注释