记一道字节跳动的算法面试题

前几天有个朋友去面试字节跳动，面试官问了他一道 链表 相关的算法题，不过他一时之间没做出来，就来问了我一下，感觉这道题还不错，拿来讲一讲。

这其实是一道 变形的链表反转题 ，大致描述如下：

给定一个单链表的头节点 head，实现一个调整单链表的函数，使得每 K 个节点之间为一组进行逆序，并且 从链表的尾部开始组起 ，头部剩余节点数量不够一组的不需要逆序。 （不能使用队列或者栈作为辅助）

例如：

链表：1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8，3->4->5，1->2 各位一组。调整后：1->2->5->4->3->8->7->6->null。其中 1，2不调整，因为不够一组。

这道题的难点在于， 是 从链表的尾部开始组起的，而 不是从链表的头部 ，如果是头部的话，那我们还是比较容易做的，因为你可以遍历链表，每遍历 k 个就拆分为一组来逆序。但是从尾部的话就不一样了，因为是单链表，不能往后遍历组起。不过这道题肯定是用递归比较好做。

在做这道题之前，我们不仿先来看看 如果从头部开始组起的话 ，应该怎么做呢？例如：链表：1->2->3->4->5->6->7->8->null, K = 3。调整后：3->2->1->6->5->4->7->8->null。其中 7，8 不调整，因为不够一组。

这道题我们可以用递归来实现，假设方法 reverseKNode() 的功能是将单链表的每 K 个节点之间逆序 (从头部开始组起的哦) ；reverse() 方法的功能是将一个单链表逆序。

那么对于下面的这个单链表，其中 K = 3。

我们把前 K 个节点与后面的节点分割出来：

temp 指向的剩余的链表，可以说是原问题的一个子问题。我们可以调用 reverseKNode() 方法将 temp 指向的链表每 K 个节点之间进行逆序。再调用 reverse() 方法把 head 指向的那 3 个节点进行逆序，结果如下：

接着，我们只需要把这两部分给连接起来就可以了。最后的结果如下：

代码如下：

   
 //k个为一组逆序
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode temp = head;
        for (int i = 1; i null; i++) {
            temp = temp.next;
        }
        //判断节点的数量是否能够凑成一组
        if(temp == null)
            return head;

        ListNode t2 = temp.next;
        temp.next = null;
        //把当前的组进行逆序
        ListNode newHead = reverseList(head);
        //把之后的节点进行分组逆序
        ListNode newTemp = reverseKGroup(t2, k);
        // 把两部分连接起来
        head.next = newTemp;

        return newHead;
    }

    //逆序单链表
    private static ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode result = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return result;
    }

这两道题可以说是及其相似的了，只是一道从头部开始组起，这道从头部开始组起的，也是 leetcode 的第 25 题。而面试的时候，经常会进行变形，例如这道字节跳动的题，它变成从尾部开始组起，可能你一时之间就不知道该怎么弄了。当然，可能有人一下子就反应出来，把他秒杀了。

其实这道题很好做滴，你只需要 先把单链表进行一次逆序，逆序之后就能转化为从头部开始组起了 ， 然后按照我上面的解法，处理完之后，把结果再次逆序即搞定。两次逆序相当于没逆序。

例如对于链表（其中 K = 3）

我们把它从尾部开始组起，每 K 个节点为一组进行逆序。步骤如下

1、先进行逆序

逆序之后就可以把问题转化为从头部开始组起，每 K 个节点为一组进行逆序。

2、处理后的结果如下

3、接着在把结果逆序一次，结果如下

代码如下