NC50：链表中的节点每k个一组翻转

3种解法
1. 栈：https://blog.csdn.net/qq_43431171/article/details/106154251
2. 模拟：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/tu-jie-kge-yi-zu-fan-zhuan-lian-biao-by-user7208t/
3. 递归：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/di-gui-java-by-reedfan-2/

解法1：栈

把 k 个数压入栈中，然后弹出来的顺序就是翻转的！
这里要注意几个问题：
第一，剩下的链表个数够不够 k 个（因为不够 k 个不用翻转）；
第二，已经翻转的部分要与剩下链表连接起来。

   public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        //定义一个栈
        Stack<ListNode> stack=new Stack<ListNode>();
        //初始化一个新的链表存放结果
        ListNode ret = new ListNode(0);
        //为新链表定义一个指针,防止后续操作改变链表头节点
        ListNode p = ret;
        //循环原有链表
        while (true){
            //为每次反转计数
            int count=0;
            //定义指针操作原始链表
            ListNode tmp = head;
            //循环入栈
            while (tmp!=null&&count<k){
                stack.push(tmp);
                tmp=tmp.next;
                count++;
            }
            //判断该次反转是否达到要求，此处防止因tem==null跳出循环的条件
            if (count!=k){
                //表示剩下的节点不够k个，直接将剩余节点插入末尾结束
                p.next=head;
                break;
            }
            //出栈操作，反转链表
            while (!stack.isEmpty()){
                p.next=stack.pop();
                p = p.next;
            }
            //重置下一次操作的初始节点
            p.next=tmp;
            head=tmp;
        }
        return ret.next;
    }

解法2：模拟法

1. 链表分区为已翻转部分+待翻转部分+未翻转部分

2. 每次翻转前，要确定翻转链表的范围，这个必须通过 k 此循环来确定

3. 需记录翻转链表前驱和后继，方便翻转完成后把已翻转部分和未翻转部分连接起来

4. 初始需要两个变量 pre 和 end，pre 代表待翻转链表的前驱，end 代表待翻转链表的末尾

5. 经过k此循环，end 到达末尾，记录待翻转链表的后继 next = end.next

6. 翻转链表，然后将三部分链表连接起来，然后重置 pre 和 end 指针，然后进入下一次循环

7. 特殊情况，当翻转部分长度不足 k 时，在定位 end 完成后，end==null，已经到达末尾，说明题目已完成，直接返回即可
   
   时间复杂度为 O(n*K) ：最好的情况为 O(n) 最差的情况为 O(n^2)
   空间复杂度为 O(1) ：除了几个必须的节点指针外，我们并没有占用其他空间

   public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null){
            return head;
        }
        //定义一个假的节点。
        ListNode dummy=new ListNode(0);
        //假节点的next指向head。
        // dummy->1->2->3->4->5
        dummy.next=head;
        //初始化pre和end都指向dummy。pre指每次要翻转的链表的头结点的上一个节点。
        //end指每次要翻转的链表的尾节点
        ListNode pre=dummy;
        ListNode end=dummy;
   
        while(end.next!=null){
            //循环k次，找到需要翻转的链表的结尾,这里每次循环要判断end是否等于空
            //因为如果为空，end.next会报空指针异常。
            //dummy->1->2->3->4->5 若k为2，循环2次，end指向2
            for(int i=0;i<k&&end != null;i++){
                end=end.next;
            }
            //如果end==null，即需要翻转的链表的节点数小于k，不执行翻转。
            if(end==null){
                break;
            }
            //先记录下end.next,方便后面链接链表
            ListNode next=end.next;
            //然后断开链表
            end.next=null;
            //记录下要翻转链表的头节点
            ListNode start=pre.next;
            //翻转链表,pre.next指向翻转后的链表。1->2 变成2->1。 
            //dummy->2->1
            pre.next=reverse(start);
            //翻转后头节点变到最后。通过.next把断开的链表重新链接。
            start.next=next;
            //将pre换成下次要翻转的链表的头结点的上一个节点。即start
            pre=start;
            //翻转结束，将end置为下次要翻转的链表的头结点的上一个节点。
            //即start
            end=start;
        }
        return dummy.next;
    }
    //链表翻转
    // 例子：   head： 1->2->3->4
    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域指向前一个节点   null<-1<-2<-3<-4
            preNode = curNode;
            //preNode 指针向后移动。preNode指向当前节点。
            curNode = nextNode;
            //curNode指针向后移动。下一个节点变成当前节点
        }
        return preNode;
   
    }

   解法3：递归

   大致过程可以分解为
   1、找到待翻转的k个节点（注意：若剩余数量小于 k 的话，则不需要反转，因此直接返回待翻转部分的头结点即可）。
   2、对其进行翻转。并返回翻转后的头结点（注意：翻转为左闭又开区间，所以本***作的尾结点其实就是下一***作的头结点）。
   3、对下一轮 k 个节点也进行翻转操作。
   4、将上一轮翻转后的尾结点指向下一轮翻转后的头节点，即将每一轮翻转的k的节点连接起来。
   

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            //剩余数量小于k的话，则不需要反转。
            if (tail == null) {
                return head;
            }
            tail = tail.next;
        }
        // 反转前 k 个元素
        ListNode newHead = reverse(head, tail);
        //下一轮的开始的地方就是tail
        head.next = reverseKGroup(tail, k);
   
        return newHead;
    }
   
    /*
    左闭又开区间
     */
    private ListNode reverse(ListNode head, ListNode tail) {
        ListNode pre = null;
        ListNode next = null;
        while (head != tail) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
   
    }