450.K组翻转链表(高频)(难题）

描述

给你一个链表以及一个k,将这个链表从头指针开始每k个翻转一下。
链表元素个数不是k的倍数，最后剩余的不用翻转。

样例

给出链表 1->2->3->4->5
k = 2, 返回 2->1->4->3->5
k = 3, 返回 3->2->1->4->5

技巧

用dummy结点的原因是第一个结点在翻转时，指向第一个结点的指针要发生变化，新建一个dummy结点可以将所有的指针变化全部封装在函数里，无需而外修改指向容易操作

代码

1. version1

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

public class Solution {
    /*
     * @param head: a ListNode
     * @param k: An integer
     * @return: a ListNode
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode curt = dummy;
        // curt返回null时说明剩余结点数目不足k个
        while (curt != null) {
            // k + 1个结点（包括新建的头结点）的.next需要变化
            curt = reverseNextK(curt, k);
        }
        // dummy虽然参与翻转，但变的是结点指向，
        // 虽然链表的头结点会改变，但dummy.next永远指向链表的入口
        return dummy.next;
    }
    
    private ListNode reverseNextK(ListNode node, int k) {
        // node -> n1 -> n2 ... nk -> nk+1 ...
        // ==>
        // node -> nk -> nk-1...n1 -> nk+1...
        // return n1
        // n1要特别标记下来，因为最后要返回n1来得到下一组k个结点的头结点，
        // 当反转后node.next就不是n1了
        ListNode n1 = node.next;
        // 给nk设置初值，nk不断遍历下一个结点，不足k个结点时，return null
        ListNode nk = node; 
        for (int i = 0; i < k; i++) {
            // 此处 nk 的后移和 if 判断语句的顺序不能颠倒，不然会出现空指针异常
            // 原因是 nk 的初始定义是 node1 的前一个结点
            nk = nk.next;
            if (nk == null) {
                return null;
            }
        }
    
        // 翻转链表的模板
        // 每k个结点reverse, nk在上面循环结束时指向了第k个结点
        // 在翻转 k 个链表前要通过 for 循环找到第 k 个结点
        ListNode nkplus = nk.next;
        ListNode prev = null;
        ListNode curt = n1;
        // null -> n1 -> n2 ... nk -> nkplus
        // ==>
        // null <- n1 <- n2 ... nk <- nkplus
        while (curt != nkplus) {
            ListNode temp = curt.next;
            curt.next = prev;
            prev = curt;
            curt = temp;
        }
        
        // connect，中间需要reverse的完成后需要把两端的指针连接好
        // node代表头结点
        // null -> nk —> nk - 1 ->...n1 -> nkplus
        node.next = nk;
        // n1和nk进行了位置交换
        n1.next = nkplus;
        return n1;
    }
}

2. version2

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * @param head a ListNode
     * @param k an integer
     * @return a ListNode
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k <= 1) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        head = dummy;
        while (head.next != null) {
            head = reverseNextK(head, k);
        }
        
        return dummy.next;
    }
    
    // reverse head->n1->..->nk->next..
    // to head->nk->..->n1->next..
    // return n1
    private ListNode reverseNextK(ListNode head, int k) {
        // check there is enought nodes to reverse
        ListNode next = head; // next is not null
        for (int i = 0; i < k; i++) {
            if (next.next == null) {
                return next;
            }
            next = next.next;
        }
        
        // reverse
        ListNode n1 = head.next;
        ListNode prev = head, curt = n1;
        for (int i = 0; i < k; i++) {
            ListNode temp = curt.next;
            curt.next = prev;
            prev = curt;
            curt = temp;
        }
        
        n1.next = curt;
        head.next = prev;
        return n1;
    }
}