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

public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        //双指针，pre代表需要反转的起始点，node用来寻找下一段反转的起始点
        ListNode node = head;
        ListNode pre = head;
        int m = 0;
        //将node定位在下一段起始点的前一位置上
        //比如K是2，数据是1，2，3，4，5；那么node定位在2上
        //因为需要断开2与3的连接
        while(m<k-1&&node!=null){
           node = node.next;
           m++; 
        }
        //如果跳出循环，node是null，那么证明长度不满足K个了，直接返回起始点
        if(node==null){
            return pre;
        }
        else{
            //断开前一段和后一段的连接
            ListNode temp = node.next;
            node.next=null;
            node = temp;
            //将当前段进行反转：1，2反转成为->2,1
            ListNode reverseNode = reverse(pre);
            //递归找下一段
            ListNode list = reverseKGroup(node,k);
            //假设这一层是1，2->反转成2->1
            //1就是最开始的起始点pre
            //2是反转得到的reverseNode；
            //所以用pre指向递归返回的list就进行了拼接
            pre.next=list;
            return reverseNode;
        }
    }
    //链表的反转
    public ListNode reverse(ListNode reverseNode){
        ListNode pre = null;
        while(reverseNode!=null){
            ListNode temp = reverseNode.next;
            reverseNode.next = pre;
            pre= reverseNode;
            reverseNode = temp;
        }
        return pre;
    }

public ListNode reverseKGroup (ListNode head, int k) {
        //哨兵
        ListNode numpy = new ListNode();
        //用来当前段的最后一个节点
        ListNode numpy1 = numpy;
        //寻找下一段的起点
        ListNode node = head;
        //记录当前段的起点
        ListNode pre  = head;
        while (node!=null){
             int m = 0;
            while(m<k-1&&node!=null){
                node = node.next;
                m++;
            }
            //如果node=null了，那么证明已经不够K个进行反转了
            if(node==null){
                break;
            }
            else{
                //定位下一段的起点
                ListNode temp = node.next;
                 //断开当前段和下一段的关联
                node.next = null;
                //下一段的起点
                node = temp;
                //通过当前段的起点进行翻转
                ListNode reverseNode = reverse(pre);
                //上一段的最后一个节点指向翻转后的当前段
                numpy1.next=reverseNode;
                //记录当前段的最后一个节点
                numpy1 = pre;
                //pre更新为下一段的起点
                pre=node;
            }
            
        }
        //因为在循环中层断开过与后一段的关联
        //如果出现了后一段不足k个的情况应该将其重新关联起来
        numpy1.next = pre;
        return numpy.next;
    }
     public ListNode reverse(ListNode reverseNode){
        ListNode pre = reverseNode;
        reverseNode = reverseNode.next;
        while(reverseNode!=null){
            ListNode temp = reverseNode.next;
            reverseNode.next = pre;
            pre= reverseNode;
            reverseNode = temp;
        }
        return pre;
    }