题解 | #链表中的节点每k个一组翻转#

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

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    /*
    k个一组的遍历链表
    若这一组有k个节点,那么把这一组节点按照头插法插入新链表的尾部(同时记录并更新新链表的尾部)
    */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        ListNode returnList = new ListNode(-1); // 定义头节点
        ListNode tail = returnList; // 记录尾部位置
        returnList.next = null;
        
        int listLength = getLength(head);
        ListNode temp = null;
        for(int i = 0; i + k <= listLength; i=i+k){
            temp = head; // 记录要翻转的起始节点
            // head 后移k次
            for(int j = 0; j < k; j++){
                head = head.next;
            }
            // 开始头插
            tail = firstAdd(tail,temp,k);
        }
        // 把剩余部分插在后面
        if(head != null){
            tail.next = head;
        }
        
        return returnList.next;
        
    }
    
    public int getLength(ListNode list){
        int length = 0;
        while(list!=null){
            list = list.next;
            length++;
        }
        return length;
    }
    // 在尾部进行头插发 , 返回新的尾
    public ListNode firstAdd(ListNode tail,ListNode reverseList, int k){
        ListNode del = null, newtail = reverseList; // 头插法,尾就是插入的第一个元素
        
        for(int i = 0; i< k; i++){
            del = reverseList;
            reverseList = reverseList.next;
            
            del.next = tail.next;
            tail.next = del;
        }
        return newtail;
    }
}