题目描述

将给出的链表中的节点每k个一组翻转，返回翻转后的链表。如果链表中的节点数不是k的倍数，将最后剩下的节点保持原样，你不能更改节点中的值，只能更改节点本身。
例如：
给定的链表是1->2->3->4->5 对于k=2，你应该返回 2->1->4->3->5 对于k=3，你应该返回 3->2->1->4->5

题目分析

题目是在链表的翻转基础上，增加了一个长度的限制k，每k个进行一次翻转，首先我们要知道如何翻转一个链表，然后需要将这些翻转的部分连接起来，链表的翻转可以使用头插法，如图：

alt

因为每次要把翻转的节点换到头部来(pre的next节点)，所以称为头插法，主要是要弄清pre，cur，tmp节点的转换以及对应的步骤等。

解题思路

方法1：头插法翻转节点，对每个部分进行循环翻转

使用循环来对部分翻转，需要确定每个部分的起始和终止节点，简单点可以先计算一下链表的长度len，然后获得需要翻转的部分数len/k，在每个部分中使用上述的头插法，每次结束一个部分需要更新pre为前一个部分的尾部节点。

方法2：头插法翻转节点，对每个部分进行递归翻转

使用递归方法，设置结束递归的条件（剩余节点数小于k），一次调用中只进行一个部分的翻转，使用dfs进行下一个部分的翻转，直到全部翻转完成。

代码实现

方法1：头插法翻转节点，对每个部分进行循环翻转

  import java.util.*;

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

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        if(k <= 1 || head == null || head.next == null) return head;
        // 设置一个虚拟头节点
        ListNode h = new ListNode(0);
        h.next = head;
        ListNode cur = head;
        ListNode tmp = null;
        ListNode pre = h;
        int len = 0;
        while(head != null){
            len++;
            head = head.next;
        }
        // 计算一共有 len/k个部分需要翻转
        for(int i=0;i<len/k;i++){
            // 每k个结点，进行一次翻转
            for(int j=1;j<k;j++){
                // 使用头插法进行翻转，不断将后面的结点放到pre的后面
                tmp = cur.next;
                cur.next = tmp.next;
                tmp.next = pre.next;
                pre.next = tmp;
            }
            // 将pre和cur移到下一个部分头部
            pre = cur;
            cur = cur.next;
        }
        return h.next;
    }
}

时间复杂度： $O (n)$ ，循环需要遍历链表的所有节点两次，所以时间复杂度为 $O (n)$ ；

空间复杂度： $O (1)$ ，在循环的过程中只需要常数级的变量，空间复杂度为 $O (1)$ 。

方法2：头插法翻转节点，对每个部分进行递归翻转

 import java.util.*;

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

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if(k <= 1 || head == null || head.next == null) return head;
        // 设置一个虚拟头节点
        ListNode h = new ListNode(0);
        h.next = head;
        ListNode next = null;
        ListNode cur = head;
        ListNode tmp = head;
        for(int i=1;i<k;i++){
            // 判断剩下的部分是否有k个，没有直接不操作返回
            cur = cur.next;
            if(cur == null) return head;
        }
        next = cur.next;
        // 使用头插法进行该部分前k个结点的翻转
        while(head.next != next){
            tmp = head.next;
            head.next = tmp.next;
            tmp.next = h.next;
            h.next = tmp;
        }
        // 递归调用进行后面的翻转
        head.next = reverseKGroup(next, k);
        return h.next;
    }
}

时间复杂度： $O (n)$ ，递归也需要遍历链表的所有节点，所以时间复杂度为 $O (n)$ ；

空间复杂度： $O (n / k)$ ，在递归的过程中栈的深度为n/k，空间复杂度为 $O (n / k)$ 。

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

题目描述

题目分析

解题思路

代码实现