1,非递归解决

每k个一组进行反转,如果不够k个就不需要反转,关于链表的反转,不会的可以看下《432,剑指 Offer-反转链表的3种方式》 。最简单的一种方式就是把链表每k个分成一组,然后反转这每一组的节点,接着在把他们串起来即可。

    public ListNode reverseKGroup(ListNode head, int k) {
        //先创建一个哑节点
        ListNode dummy = new ListNode(0);
        //让哑节点的指针指向链表的头
        dummy.next = head;
        //开始反转的前一个节点,比如反转的节点范围是[link1,link2],
        //那么pre就是link1的前一个节点
        ListNode pre = dummy;
        ListNode end = dummy;
        while (end.next != null) {
            //每k个反转,end是每k个链表的最后一个
            for (int i = 0; i < k && end != null; i++)
                end = end.next;
            //如果end是空,说明不够k个,就不需要反转了,直接退出循环。
            if (end == null)
                break;
            //反转开始的节点
            ListNode start = pre.next;
            //next是下一次反转的头结点,先把他记录下来
            ListNode next = end.next;
            //因为end是这k个链表的最后一个结点,把它和原来链表断开,
            //这k个节点我们可以把他们看做一个小的链表,然后反转这个
            //小链表
            end.next = null;
            //因为pre是反转链表的前一个节点,我们把小链表[start,end]
            //反转之后,让pre的指针指向这个反转的小链表
            pre.next = reverse(start);
            //注意经过上一步反转之后,start反转到链表的尾部了,就是已经
            //反转之后的尾结点了,让他之前下一次反转的头结点即可(上面分析
            //过,next就是下一次反转的头结点)
            start.next = next;
            //前面反转完了,要进入下一波了,pre和end都有重新赋值
            pre = start;
            end = start;
        }
        return dummy.next;
    }

    //链表的反转
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

2,递归方式解决

这里并不是反转全部的节点,而是每k个节点进行反转,递归调用,直到不能完全反转为止,如果对于递归不了解的可以先看下《426,什么是递归,通过这篇文章,让你彻底搞懂递归》

看下代码

    public ListNode reverseKGroup(ListNode head, int k) {
        //边界条件判断
        if (head == null || head.next == null)
            return head;
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            //剩余数量小于k的话,则不需要反转。
            if (tail == null)
                return head;
            tail = tail.next;
        }
        // 反转前 k 个元素
        ListNode newHead = reverse(head, tail);
        //下一轮的开始的地方就是tail
        head.next = reverseKGroup(tail, k);
        return newHead;
    }

    /*
        链表的反转,不是反转全部,只反转区间[head,tail)中间的节点,左闭右开区间
     */
    private ListNode reverse(ListNode head, ListNode tail) {
        ListNode pre = null;
        ListNode next = null;
        while (head != tail) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的《牛客博客》查看更多的详细题解