25.K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

**输入：** head = [1,2,3,4,5], k = 2
**输出：** [2,1,4,3,5]

示例 2：

**输入：** head = [1,2,3,4,5], k = 3
**输出：** [3,2,1,4,5]

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

进阶： 你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */


//关键：新增哑节点，因为部分翻转后需要进行首尾连接，需要记下第一个断开的节点和尾节点

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        //双指针用来操作翻转
        ListNode first=new ListNode();
        ListNode tail=head;
        //手动添加first为第一个哑巴节点
        first.next=head;
        ListNode ans=first;
        
        while(tail!=null){
            int n=k-1;
            //查找翻转的部分
            while(n>0&&tail.next!=null){
                tail=tail.next;
                n--;
            }
            //记录下一组要翻转的第一个节点，因为在翻转过程中tail节点会往前移动
            ListNode temp_tail=tail.next;

            //如果不够n个节点翻转，说明链表走完了
            if(n!=0)
                return ans.next;
            //翻转节点
            else{
                while(first.next!=tail){
                //取出第一个节点
                ListNode temp=first.next;
                //头结点跳过第一个节点，连接下一个节点
                first.next=temp.next;
                //第一个节点连接尾节点的下一个位置
                temp.next=tail.next;
                //尾节点连接第一个节点
                tail.next=temp;
                }
            
                //刚好够组数
                //if(temp_tail==null)
                //    return ans.next;改成整个大while判断

                //开始准备下一组的first和tail    
                tail=temp_tail;
                while(first.next!=tail)
                    first=first.next;
            }
        }
        return ans.next;
    }
}