真题描述:反转从位置 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、nconst reverseBetween = function(head, m, n) {// 定义pre、cur,用leftHead来承接整个区间的前驱结点let pre,cur,leftHead// 别忘了用 dummy 嗷const dummy = new ListNode()// dummy后继结点是头结点dummy.next = head// p是一个游标,用于遍历,最初指向 dummylet 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 指向startpre = start// cur 指向 start 的下一个结点cur = pre.next// 开始重复反转动作for(let i=m;i<n;i++){let next = cur.nextcur.next = prepre = curcur = next}// leftHead 的后继结点此时为反转后的区间的第一个结点leftHead.next = pre// 将区间内反转后的最后一个结点 next 指向 curstart.next=cur// dummy.next 永远指向链表头结点return dummy.next};
