链表内指定区间反转

在此之前，我们可以来看比较简单的反转链表：

• 迭代法：
  相当于看成是两个大节点，一个是head，一个是ReverseList

  public class Solution {
  
    public ListNode ReverseList(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return head;
        ListNode pre = null;
        ListNode next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
  }

• 递归法：
  可以将整个链表看成只有head节点和reverseList节点，然后进行反转。返回的是反序后的头结点。
  

  public class Solution {
  
    public ListNode ReverseList(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return head;
        ListNode last = ReverseList(head.next); //三步  last节点为reverseList
        head.next.next = head; //反转last节点
        head.next = null; //反转head节点
        return last; //返回last节点
    }
  }

这道题是上面的扩展：
我们也可用迭代法和递归法：

迭代法比较好理解：

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {

        ListNode pre = null;
        ListNode post = null;    //分别保存子链的前一个节点和后一个节点
        ListNode begin = null;
        ListNode end = null;    //分别保存子链的第一个节点和最后一个节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy;    //从头结点开始
        int cnt = 0;
        while(cnt <= n){
            if(cnt+1 == m){    //找到子链的前一节点和第一节点
                pre = p;
                begin = p.next;
            }
            if(cnt == n){    //找到子链的后一节点和最后节点
                end = p;
                post = p.next;
            }
            ++cnt; 
            p = p.next;

        }

        ListNode q = begin;
        p = begin.next;
        while(p != post){    //开始反转
            ListNode next = p.next;    //保存反转目标节点的下一个节点
            p.next = q;
            q = p;
            p = next;
        }
        //重新合链
        pre.next = end;
        begin.next = post;
        return dummy.next;

    }
}

递归法：

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // base case
        if(m == 1){
            return reverseN(head,n);
        }
        //递归到反转的起点，触发反转的起点 base case
        head.next = reverseBetween(head.next, m-1, n-1);
        return head;
    }
    ListNode post = null;
    /**
    *    反转以head为起点的n个节点，返回新的头结点
    */
    public ListNode reverseN(ListNode head, int n){
        if(n == 1){
            //记录第n+1个节点，后面合链时要用
            post = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n-1);
        head.next.next = head;
        head.next = post;
        return last;
    }
}

这两者的时间复杂度都是O(N)，而迭代的空间复杂度为O(1)，递归的是O(N)，因为需要堆栈。
所以建议用迭代算法

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        if(head == null || head.next == null)
                return head;

        //定义哑节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //初始化pre和end都指向dummy。pre指每次要反转的链表的头结点的上一个节点。end指的是每次要反转的链表的尾结点
        ListNode pre = dummy;
        ListNode end = dummy;
        while(end.next != null){
            //循环k次，找到需要反转的链表的结尾
            //每次循环都要end判空，因为如果为空，end.next会报空指针异常
            for(int i=0; i < k && end != null; i++){
               end = end.next;
            }
            //如果end为空，即需要反转的链表节点数小于k，不执行反转
            if(end == null)
                break;

            //先记录下end.next,方便后面链接链表
            ListNode next = end.next;
            //然后断开链表
            end.next = null;
            //记录要反转链表的头结点
            ListNode start = pre.next;
            //反转链表，pre.next指向反转后的链表
            pre.next = reverse(start);
            //反转后头结点变到最后，通过.next把断开的聊表重新链接
            start.next = next;
            //将pre换成下次要反转的链表的头结点的上一个节点，即start
            pre = start;
            //将end置为下次要反转的链表的头结点的上一个节点
            end = start;
        }
        return dummy.next; 
    }

    public ListNode reverse(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        //前一个节点指针
        ListNode preNode = null;
        //当前节点指针
        ListNode curNode = head;
        //下一个节点指针
        ListNode nextNode = null;
        while(curNode != null){
            nextNode = curNode.next; //nextNode 指向下一个节点，保存当前节点后面的链表
            curNode.next = preNode; //将当前节点next指向前一个节点
            preNode = curNode; //preNode向后移动 preNode指向当前节点
            curNode = nextNode; //curNode指针向后移动， 下一个节点变成当前节点
        }
        return preNode;
    }
}