【力扣刷题】25. K 个一组翻转链表

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

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

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

输入： head = [1], k = 1
输出： [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) {
        int len=0;                  //统计链表的长度
        ListNode plen=head;
        while(plen!=null){
            len++;
            plen=plen.next;
        }

        int reverse_times=len/k;     //计算链表的翻转次数
        if(k<=1 || reverse_times==0){
            return head;
        }

        ListNode knext=head;         //保存下一次翻转时候的链表头结点
        int cur_times=0;      //保存当前翻转次数
        ListNode nhead=new ListNode(-1);    //虚拟头结点，不包含任何数据
        ListNode cur_head=nhead;
        cur_head.next=head;
        ListNode cur_tail=null;
        while(cur_times<reverse_times){
            //将knext指向下一次翻转时候的链表头结点
            for(int i=0;i<k;i++){
                knext=knext.next;
            }

            //使用头插法进行反转            
            ListNode p=cur_head.next;        //保存当前需要头插的结点
            cur_tail=cur_head.next;
            ListNode next=null;         //保存反转时下一个结点的指针
            for(int i=0;i<k;i++){
                next=p.next;           
                p.next=cur_head.next;
                cur_head.next=p;
                p=next;
            }
            //将尾部结点重新赋值给头部结点，并且让尾部结点的next指针指向knext
            cur_head=cur_tail;
            cur_tail.next=knext;
            // System.out.println("3 "+knext.val);
            cur_times++;
        }        
        return nhead.next;
    }
}