给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

    示例 1:
    输入:head = [1,2,3,4,5], left = 2, right = 4
    输出:[1,4,3,2,5]

    image.png

    示例 2:
    输入:head = [5], left = 1, right = 1
    输出:[5]

    image.png

    第一步:从虚拟结点开始走 m - 1 步,确定 precursor 节点,即需要反转部分的前一个节点
    第二步:继续走 n - m + 1,确定 successor 节点,即需要反转部分的后面一个节点
    第三步:把 precursor 节点 和 successor 节点中间部分的链表进行反转
    第四步:让 precursor 节点的 next 指针指向 中间部分反转后的头节点
    第五步:让 中间部分反转后的尾节点的 next 指针指向 successor 节点

    1. public ListNode reverseBetween(ListNode head, int left, int right) {
    2. // 因为头节点有可能发生变化,使用虚拟头节点可以避免复杂的分类讨论
    3. ListNode dummyNode = new ListNode(-1);
    4. dummyNode.next = head;
    5. ListNode precursorNode = dummyNode;
    6. // 第 1 步:从虚拟头节点走 left - 1 步,来到 left 节点的前一个节点
    7. for (int i = 0; i < left - 1; i++) {
    8. precursorNode = precursorNode.next;
    9. }
    10. // 第 2 步:从 pre 再走 right - left + 1 步,来到 right 节点
    11. ListNode rightNode = precursorNode;
    12. for (int i = 0; i < right - left + 1; i++) {
    13. rightNode = rightNode.next;
    14. }
    15. // 第 3 步:切断出一个子链表(截取链表)
    16. ListNode leftNode = precursorNode.next;
    17. precursorNode.next = null;
    18. rightNode.next = null;
    19. // 第 4 步:反转截取的链表
    20. reverseList(leftNode);
    21. // 第 5 步:接回到原来的链表中
    22. precursorNode.next = rightNode;
    23. leftNode.next = rightNode.next;
    24. return dummyNode.next;
    25. }
    26. public ListNode reverseList(ListNode head) {
    27. ListNode dummy = new ListNode();
    28. while (head.next != null) {
    29. ListNode temp = head.next;
    30. temp.next = dummy.next;
    31. dummy.next = temp;
    32. head = head.next;
    33. }
    34. return dummy.next;
    35. }