真题描述:反转从位置 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上。

    1. /**
    2. * @param {ListNode} head
    3. * @param {number} m
    4. * @param {number} n
    5. * @return {ListNode}
    6. */
    7. // 入参是头结点、m、n
    8. const reverseBetween = function(head, m, n) {
    9. // 定义pre、cur,用leftHead来承接整个区间的前驱结点
    10. let pre,cur,leftHead
    11. // 别忘了用 dummy 嗷
    12. const dummy = new ListNode()
    13. // dummy后继结点是头结点
    14. dummy.next = head
    15. // p是一个游标,用于遍历,最初指向 dummy
    16. let p = dummy
    17. // p往前走 m-1 步,走到整个区间的前驱结点处
    18. for(let i=0;i<m-1;i++){
    19. p = p.next
    20. }
    21. // 缓存这个前驱结点到 leftHead 里
    22. leftHead = p
    23. // start 是反转区间的第一个结点
    24. let start = leftHead.next
    25. // pre 指向start
    26. pre = start
    27. // cur 指向 start 的下一个结点
    28. cur = pre.next
    29. // 开始重复反转动作
    30. for(let i=m;i<n;i++){
    31. let next = cur.next
    32. cur.next = pre
    33. pre = cur
    34. cur = next
    35. }
    36. // leftHead 的后继结点此时为反转后的区间的第一个结点
    37. leftHead.next = pre
    38. // 将区间内反转后的最后一个结点 next 指向 cur
    39. start.next=cur
    40. // dummy.next 永远指向链表头结点
    41. return dummy.next
    42. };