25. K 个一组翻转链表

/**
 * 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 dummyHead = new ListNode(0,head);
        ListNode pre = dummyHead;
        //1 分组，往后走K-1步，找到一组 找到一组内的head 和 end 
        while(head != null){
            ListNode groupEnd = getGroupEnd(head,k-1);
            if(groupEnd == null){
                break;
            }
            //2 每一组内部要进行翻转
            ListNode nextGroupHead = groupEnd.next;
            reverseList(head,nextGroupHead);
             //3 更新每组前一组后一组的边
             //接边
             pre.next = groupEnd;
             head.next = nextGroupHead;
             //移动pre 和 head
             pre = head;
             head = nextGroupHead;
        }
        return dummyHead.next;
    }
    //获取一个组的末尾结点
    ListNode getGroupEnd(ListNode head,int step){
        for(int i = 0;i < step;i++){
            if(head == null){
                return null;
            }
            head = head.next;
        }
        return head;
    }
    public ListNode reverseList(ListNode head, ListNode end) {
        //使用三个指针记录，pre 前面的节点，cur 当前节点，next 下一个节点
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur != end){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}