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

心路历程

问题：刚开始，做这道题，只是默默呼呼的理解，没有调试到位，理解也不到位，所以，即使做了这道题，后面回来再看，还是无法做，也不理解过程，这就是典型的一知半解。

解决：

1）深入调试，极简数据，一步步调试，观察变量的一个个变化，深入理解整个过程和原理；

2）深入思考，为什么是这一步设置的是这个变量？返回的是这个变量？

3）画流程图，理解了原理后，就画出流程图，来解答我的困惑，理解算法运作过程

4）盲敲代码， 再一步加深理解，算法的过程和原理，为什么是这一步设置的是这个变量？返回的是这个变量？

解题思路

对于一个有5个元素的链表num[5], 每k个一组翻转，非常简单，只有四步：

1、链表走k步，获取到当前翻转组的尾节点，也就是下一组的头节点，tail；

2、翻转当前链表的 [head, tail)；

3、让当前链表尾 head.next 获取剩余链表的翻转结果；

4、返回链表的结果pre。

这里要注意的几个点：

第一步，k不能直接操作和使用，因为要递归使用，改变了值，会影响后面

第二步，翻转链表，不像全链表翻转的判断尾部为null，这里是用tail判断尾部

第三步，用head.next 去接剩余链表翻转结果，而不是pre.next，

因为pre已经被翻转成头了，而head这是成为了新的队尾，接在pre的尾部。

第四步，用pre返回最终的结果，而不是用ListNode res = new ListNode(0)，return res.next。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 链表中的节点每k个一组翻转
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // 先找出下个翻链表头
        // 作为当前链表结束标志
        // 也传给下个链表递归用
        ListNode tail = head;
        int i=k;
        while(i > 0) {
            if(tail==null) {
                return head;
            }
            tail = tail.next;
             i--;
        }

        // 翻转当前链表
        ListNode cur = head;
        ListNode pre = null; // 这个操作会导致pre尾部为空，断开了与后面链表的连接，
                             // 不过没有关系，tail会递归返回排序好的结果，拼接回来
        while(cur!=tail) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }

        // 递归调用让后面去返回剩余部分的排序好的链表
        head.next = reverseKGroup(tail, k);
        return pre;  //对链表翻转，结果值都是pre，而不是head了，当前的head只有头元素
    }
     
}