BM3 将链表中的节点每k个一组翻转

BM3链表中的节点每k个一组翻转

最近在刷牛客上的编程题，记录一下~

描述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

数据范围：0≤n≤2000 ，1≤k≤2000，链表中每个元素都满足 0≤val≤1000
要求空间复杂度 O(1)，时间复杂度 O(n)

例如：

给定的链表是 1→2→3→4→5

对于 k=2 , 你应该返回 2→1→4→3→5

对于 k=3 , 你应该返回 3→2→1→4→5

示例1

输入：

{1,2,3,4,5},2

复制

返回值：

{2,1,4,3,5}

复制

示例2

输入：

{},1

复制

返回值：

{}

解决思路：

大致分为以下三个步骤：

• 首先对链表进行分组

• 组内翻转

• 翻转后的连接

  **难点：**翻转后，每一组原始链表的头节点对应的是翻转后的尾节点，原始链表的尾节点是翻转后的头节点，如果我们采用顺序对每一个分组进行处理的话，如果不建立新链表可能会很麻烦。

  解决办法：如果我们采用递归的方式从最后的一个组开始翻转，得到了最后一个组的链表首，是不是可以直接连在倒数第二个组翻转后的尾（即翻转前的头）后面。

如果这个链表有n个分组可以反转，我们首先对第一个分组反转，那么是不是接下来将剩余n−1个分组反转后的结果接在第一组后面就行了，那这剩余的n−1组就是一个子问题。我们来看看递归的三段式模版：

1. 终止条件： 当进行到最后一个分组，即不足k次遍历到链表尾（0次也算），就将剩余的部分直接返回。
2. 返回值： 每一级要返回的就是翻转后的这一分组的头，以及连接好它后面所有翻转好的分组链表。
3. 本级任务： 对于每个子问题，先遍历k次，找到该组结尾在哪里，然后从这一组开头遍历到结尾，依次翻转，结尾就可以作为下一个分组的开头，而先前指向开头的元素已经跑到了这一分组的最后，可以用它来连接它后面的子问题，即后面分组的头。

具体做法：

• step 1：每次从进入函数的头节点优先遍历链表k次，分出一组，若是后续不足k个节点，不用反转直接返回头。
• step 2：从进入函数的头节点开始，依次反转接下来的一组链表，反转过程同就如普通的翻转链表一样
• step 3：这一组经过反转后，原来的头变成了尾，后面接下一组的反转结果，下一组采用上述递归继续。

图示：

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
        
        // 声明每一组要翻转节点的尾部，作为head参数传递给下一组使用
        ListNode tail = head;
        // 遍历k次找到尾部
        for(int i = 1; i <= k; i++){
    
            // 如果为空，说明剩下的节点以及不足K个
            if(tail == null)
                return head;
            tail = tail.next;
        }    
        
        // 翻转当前组的节点
        ListNode pre = null;
        ListNode temp = null;
        ListNode cur = head;
        while(cur != tail){
    
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        
        // 现在的head指针已经是每一组的尾节点
        // 只需要将当前组的head指针指向下一个组的返回值（原始链表的尾节点，反转后的头节点）
        head.next = reverseKGroup(tail, k);
        
        // 返回当前组反转后链表的头指针（即原链表的尾节点）
        return pre;
        
    }
}