【每日一道算法题】将给出的链表中的节点每k个一组翻转，返回翻转后的链表

将给出的链表中的节点每k个一组翻转，返回翻转后的链表 如果链表中的节点数不是k的倍数，将最后剩下的节点保持原样 你不能更改节点中的值，只能更改节点本身。 要求空间复杂度O(1) 例如： 给定的链表是1→2→3→4→5 对于k=2, 你应该返回2→1→4→3→5 对于k=3, 你应该返回3→2→1→4→5

题解一：最简单的方式就是把链表每K个一组，然后分别反转，最后将它们相连。

解法：分组反转连接

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        //创建一个哑节点辅助
        ListNode dummy = new ListNode(0);
        dummy.next=head;
        //开始反转
        //pre开始反转的前一个节点，很明显为dummy
        //end节点位置在循环中确定，end没有下一个节点为循环结束的标志
        ListNode pre = dummy;
        ListNode end  = dummy;
        while(end.next!=null){
            //每k个节点反转，end是每k个的最后一个
            for(int i=0;i<k;i++){
                end=end.next;
            }
            if(end==null) break;//说明不够k个节点 直接退出循环
            //反转的开始节点
            ListNode start =pre.next;
            //记录一下下一次反转的头节点
            List next =end.next;
            //准备将小链进行反转，但是要先将[start，end]从链表上摘下来
            end.next=null;
            //进行反转
            pre.next=reverseNode(start);
            //反转之后,start反转到链表尾部，让它与下一次反转的头节点进行连接
            start.next=next;
            pre=start;
            end=start;
        }
        return dummy;
    }
    
    //反转链表
    public ListNode reverse(ListNode head){
        ListNode pre=null;
        ListNode temp=null;
        while(head!=null){
            temp=head.next;
            head.next=pre;
            pre=head;
            head=temp;        
        }
        return pre;
    }
}

题解二：通过递归实现
    1.先找到要翻转的k个节点，若剩余节点小于k则不需要翻转，只需要直接返回头节点即可
    2.对k个节点进行翻转，并返回翻转后的头节点，即本次操作后的尾节点即为下次操作的头节点（翻转为左闭右开区间）。
    3.递归翻转k个节点
    4.将上一次翻转后的尾节点指向下一轮翻转后的头节点，也就是连接操作。

解法二：递归实现

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

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 tail=head;
        for(int i=0;i<k;i++){
            //剩余数量不够k个节点，不需要翻转
            if(tail==null){
                return tail;
            }
            tail=tail.next;
        }
        //翻转k个元素
        ListNode res=reverseNode(head,tail);
        //递归调用，下一轮开始的节点即为tail
        head.next=reversKGroup(tail,k)
        return res;
    }
    /**
     * 翻转链表 
     * 左开右闭区间 tail为临界值
     * @param head ListNode类 
     * @param tail ListNode 
     * @return ListNode类
     */
     public ListNode reverseNode(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;
     }
}

题解三:通过栈来辅助实现
    根据栈的特性FILO，一次入栈出栈过程即可达到翻转效果
    1.注意k的限制，如果栈内元素不够k个不需要翻转。
    2.已经翻转（出栈）的部分与剩下部分相连。
    

解法三：通过栈实现

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
          //定义一个栈
          Stack<ListNode> stack = new Stack<ListNode>();
          //存储结果链表
          ListNode res = new ListNode(0);
          //为新链表定义一个指针，防止后续操作改变头节点
          ListNode p = res;
          //循环链表
          while(true){
              //定义指针操作原始链表
              ListNode temp =head;
              int count =0;
              //循环入栈
              while(tem!=null&&count<k){
                  stack.push(temp);
                  temp=temp.next;
                  count++
              }
              if(count!=k){
                  //剩下节点不够k个，直接将剩余节点插入末尾
                  p.next =head;
              }
              //出栈操作
              while(!stack.isEmpty()){
                  p.next=stack.pop();
                  p=p.next;
              }
              //重置下一次操作的初始节点
              p.next=temp;
              head=temp;
          }
          return res.next;
    }
}