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

复制

返回值：

{}

解决思路：

It is roughly divided into the following three steps：

• First group the linked list

• Flip within groups

• The flipped connection

  **难点：**翻转后,每一组The head node of the original linked list corresponds to the flipped tail node,The tail node of the original linked list is the flipped head node,If we process each packet sequentially,It can be cumbersome to not create a new linked list.

  解决办法：如果我们采用递归的方式Start flipping from the last group,得到了最后一个组的链表首,是不是可以直接连在倒数第二个组翻转后的尾（即翻转前的头）后面.

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

1. 终止条件： 当进行到最后一个分组,即不足k次遍历到链表尾（0次也算）,就将剩余的部分直接返回.
2. 返回值： Each level to return isThe flipped header of this packet,以及Concatenate all the flipped grouped linked lists behind it.
3. 本级任务： 对于每个子问题,先遍历k次,找到该组结尾在哪里,然后从这一组开头遍历到结尾,依次翻转,结尾就可以作为下一个分组的开头,而The element that previously pointed to the beginning has gone to the end of the group,可以Use it to connect the sub-questions behind it,即The header of the following packet.

具体做法：

• step 1：每次从进入函数的头节点优先遍历链表k次,分出一组,若是后续不足k个节点,不用反转直接返回头.
• step 2：从进入函数的头节点开始,依次反转接下来的一组链表,The reversal process is the same as a normal flipped linked list
• 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
        
        // Declare the tail of each set of nodes to be flipped,作为headThe parameters are passed to the next group for use
        ListNode tail = head;
        // 遍历ktimes to find the tail
        for(int i = 1; i <= k; i++){
    
            // 如果为空,Explain the remaining nodes and deficienciesK个
            if(tail == null)
                return head;
            tail = tail.next;
        }    
        
        // Flip the current group of nodes
        ListNode pre = null;
        ListNode temp = null;
        ListNode cur = head;
        while(cur != tail){
    
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        
        // 现在的headThe pointer is already the tail node of each group
        // Just change the current groupheadA pointer to the return value of the next group（The tail node of the original linked list,反转后的头节点）
        head.next = reverseKGroup(tail, k);
        
        // Returns the head pointer of the linked list after the current group is reversed（即原链表的尾节点）
        return pre;
        
    }
}