k个一组翻转链表

k个一组翻转链表

本题其实和206. 反转链表性质差不多，只不过一个是将整个链表翻转，一个是k个一组进行翻转。

所以可以考虑先写一个翻转链表的函数ListNode reverseList(ListNode head, int k)，传入开始翻转的链表头结点，以及参数k，限制该函数翻转的节点个数。

为了使头节点和其他节点的处理方式一致，引入虚拟头节点dummyHead指向head，这样可以使代码不用专门考虑头节点的情况。

ListNode dummyHead = new ListNode();
dummyHead.next = head;

设置一个探针probe，当探测到剩下的结点数目不够翻转时，直接跳出循环即可。

int cnt; // 用于计算往后k个节点
while(cur != null && probe != null){ // 当probe探测到不足k个节点时，break
    cnt = 0;
    while(i < k && probe != null){
        probe = probe.next;
        cnt ++;
    }
    // 当剩下节点数目有k个时，进行翻转
    if(probe != null){
        // 需要保存下一个待翻转的头节点
        ListNode temp = probe.next;
        // 接住翻转后的新的头节点
        ListNode newHead = reverseK(cur, k); 
        // 上一个节点指向新头节点
        pre.next = newHead;
        // cur此时为新链表的尾结点，指向下一个头节点
        cur.next = temp;
        // 将pre更新为cur，即下一条待翻转链表的前一个节点
        pre = cur;
        // 注意，此时探针的指向也需要改变，因为刚才翻转后，probe的指向是新的头节点
        probe = cur;
        // cur更新为下一个待翻转链表的头节点
        cur = temp;
    }
}

最后，返回dummyHead.next即可。

整体代码如下。

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null)
            return null;
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = head, probe = dummyHead, pre = dummyHead;
        int cnt;
        while(cur != null && probe != null){
            cnt = 0;
            while(i < k && probe != null){
                probe = probe.next;
                cnt ++;
            }
            if(probe != null){
                ListNode temp = probe.next;
                ListNode newHead = reverseList(cur, k); 
                pre.next = newHead;
                cur.next = temp;
                pre = cur;
                probe = cur;
                cur = temp;
            }
        }
        return dummyHead.next;
    }   
    private ListNode reverseList(ListNode head, int k){
        ListNode cur = head, pre = null;
        int count = 0;
        while(cur != null && count < k){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
            count ++;
        }
        return pre;
    }
}