【每日一道算法题】将给出的链表中的节点每\ k 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;
    }
}

复制代码