image-20210909090441416.png

1.理解题意

首先这还是反转链表系列的题目了， 是让我们反转第m到n个结点，前面我们只讲了反转链表的前n个结点，这下有上升了难度，但仔细想一想，很容易想到一个简单明了的方法，既然我们会反转前n个结点的链表，那我们就要将题目转换到我们熟悉的题目上，不就能够解决了吗？所谓举一反三，就是当我们掌握了一个核心的要点后，能够解决以该核心要点扩展的其他问题，这在刷题中是很重要的，也同样是刷题过程中，我们应该锻炼的能力。

2.解题思路

2.1.移动指针法

为何叫作移动指针法呢？主要是因为我不会起名了哈哈哈…这个方法我想我们大多数人都能够直接想到，就是将头结点的指针移动到起始结点（第m个结点的位置），然后使用然后就能当作反转链表前n个结点来做了，思路还是挺简单的。

反转链表m_n.jpg

  1. public ListNode reverseBetween(ListNode head, int left, int right) {
  2.     //反转一个节点，则直接返回
  3.     if(right-left < 1) return head;
  4.     //left==1，相当于反转前k个链表
  5.     if(left == 1) return reverseK(head, right-left+1);
  6.     //先移动到要反转的位置，并记录前一个结点
  7.     ListNode cur = head;
  8.     ListNode pre = head;//保存第m个结点的前驱结点，用于连接返回的反转链表
  9.     for (int i = 1; i < left; i++){
  10.         pre = cur;
  11.         cur = cur.next;
  12.     }
  13.     pre.next = reverseK(cur, right-left+1);
  14.     return head;
  15. }
  17. public ListNode reverseK(ListNode head, int k){
  18.     if(k == 1) return head;
  19.     ListNode Last = reverseK(head.next, k-1);
  20.     ListNode tail = head.next.next;
  21.     head.next.next = head;
  22.     head.next = tail;
  23.     return Last;
  24. }

2.2.递归法

这个方法其实也不难，只是如果对递归不是很熟悉的话，一般确实不好想的到。

让我们回顾一下反转链表中的那个递归的思想，不就是当前问题我们解决不了，但这个问题和另一个相同的子问题有关系（也就是可以由另一个问题的结果推出来），从而形成了一个递推关系，直到这个问题的不能也不用由另一个相同的子问题推出时，也就是当前问题是可解决的，当我们得到这个可解决问题的结果后，反推回去，最终就解决了我们原来要解决的问题。

好，回顾完这个思想之后，我们就来看看，我们要解决的问题，有没有这样一个递推关系和一个可解决问题。

假如我们要反转的链表是这样的：reverseBetween(head, 3, 5)

反转链表m_n_2.jpg

我们发现这个问题没法直接解决，那如果是这样呢？reverseBetween(head, 2, 4)

反转链表m_n_3.jpg

还是没有办法，那就继续直到不能往下为止，reverseBetween(head, 1, 3)

反转链表m_n_4.jpg

最终找到了我们能够解决的问题啦，left=1不就相当于是反转链表的前n个结点吗？不就正好符合我们上面所说的递归的思想吗？找到一个递归关系和一个可解决问题，由这个可解决问题反推出原问题。

public ListNode reverseBetween(ListNode head, int left, int right) {
    if(head == null) return null;
    if(left == 1){
        return reverseK(head, right);
    }
    head.next = reverseBetween(head.next, left-1, right-1);
    return head;
}
public ListNode reverseK(ListNode head, int k){
    if(k == 1) return head;
    ListNode Last = reverseK(head.next, k-1);
    ListNode tail = head.next.next;
    head.next.next = head;
    head.next = tail;
    return Last;
}