真题描述:反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL
注意⚠️:
我们遍历链表的顺序是从前往后遍历,那么为了避免结点1和结点2随着遍历向后推进被遗失,我们需要提前把1结点缓存下来。而结点5就没有这么麻烦了:随着遍历的进行,当我们完成了结点4的指针反转后,此时 cur 指针就恰好指在结点5上。
/**
* @param {ListNode} head
* @param {number} m
* @param {number} n
* @return {ListNode}
*/
// 入参是头结点、m、n
const reverseBetween = function(head, m, n) {
// 定义pre、cur,用leftHead来承接整个区间的前驱结点
let pre,cur,leftHead
// 别忘了用 dummy 嗷
const dummy = new ListNode()
// dummy后继结点是头结点
dummy.next = head
// p是一个游标,用于遍历,最初指向 dummy
let p = dummy
// p往前走 m-1 步,走到整个区间的前驱结点处
for(let i=0;i<m-1;i++){
p = p.next
}
// 缓存这个前驱结点到 leftHead 里
leftHead = p
// start 是反转区间的第一个结点
let start = leftHead.next
// pre 指向start
pre = start
// cur 指向 start 的下一个结点
cur = pre.next
// 开始重复反转动作
for(let i=m;i<n;i++){
let next = cur.next
cur.next = pre
pre = cur
cur = next
}
// leftHead 的后继结点此时为反转后的区间的第一个结点
leftHead.next = pre
// 将区间内反转后的最后一个结点 next 指向 cur
start.next=cur
// dummy.next 永远指向链表头结点
return dummy.next
};