卧槽！字节跳动的面试算法题，实在太变态了

「爱情、让人受尽委屈。」 2022-12-12 15:12 178阅读 0赞

点击上方“**五分钟学算法**”，选择“星标”公众号

重磅干货，第一时间送达![format_png][]

![format_png 1][]

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

### 题目 ###

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

给定一个单链表的头节点 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 个就拆分为一组来逆序。但是从尾部的话就不一样了，因为是单链表，不能往后遍历组起。不过这道题肯定是用递归比较好做，对递归不大懂的建议看我之前写的一篇文章[身为技术专家的我，面试居然还要靠刷题?][Link 1]这篇文章写了关于递归的一些套路。

### 先做一道类似的反转题 ###

在做这道题之前，我们不仿先来看看**如果从头部开始组起的话**，应该怎么做呢？例如：链表: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。

![format_png 2][]

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

![format_png 3][]

temp指向的剩余的链表，可以说是原问题的一个子问题。

我们可以调用reverseKNode()方法将temp指向的链表每K个节点之间进行逆序。

再调用reverse()方法把head指向的那3个节点进行逆序，结果如下：

![format_png 4][]

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

![format_png 5][]

代码如下：

//k个为一组逆序
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode temp = head;
            for (int i = 1; i < k && temp != 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）

![format_png 2][]

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

步骤如下：

**1、先进行逆序**

![format_png 6][]

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

**2、处理后的结果如下**

![format_png 7][]

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

![format_png 8][]

代码如下：

public ListNode solve(ListNode head, int k) {
        // 调用逆序函数
        head = reverse(head);
        // 调用每 k 个为一组的逆序函数（从头部开始组起）
        head = reverseKGroup(head, k);
        // 在逆序一次
        head = reverse(head);
        return head;
    
    }

类似于这种需要先进行逆序的还要两个链表相加，这道题字节跳动的笔试题也有出过，如下图的第二题：

![format_png 9][]

这道题就需要先把两个链表逆序，再节点间相加，最后在合并了。

### 总结 ###

关于链表的算法题，在面试的时候听说是挺常考的，大家可以多注意注意。

--------------------

### **推荐阅读** ###

• [吴师兄实名吐槽 LeetCode 上的一道题目。。。][LeetCode]• [面试字节跳动时，我竟然遇到了原题……][Link 2]• [计算机专业的学生怎样练习编程才能把编程学精通？][Link 3]• [为什么 MySQL 使用 B+ 树][MySQL _ B_]• [一道简简单单的字节跳动算法面试题][Link 4]

--------------------

欢迎关注我的公众号“**五分钟学算法**”，如果喜欢，麻烦点一下“**在看**”~

![format_png 10][]

[format_png]: /images/20221123/706dd982e604485e8b9c42e9de8032f8.png
[format_png 1]: /images/20221123/d873cea376344a2e8327cc0aa85fa3ef.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzIyMjQ0MTU0NA%3D%3D&chksm=e82c2f45df5ba65362aec958110aea84477c3ba5f81557dd335a1546a58f72bd8f60f5b4f4a9&idx=1&mid=2247489122&scene=21&sn=dcc731eef0e96a9d8fa59a1bfbeed333#wechat_redirect
[format_png 2]: /images/20221123/18097cc20a4048969ffadcf00a0f81af.png
[format_png 3]: /images/20221123/f67c6ccc79214fd189e1efbd8ac37bd1.png
[format_png 4]: /images/20221123/97daa47990bb4fa3ac3cd9492c3e16b0.png
[format_png 5]: /images/20221123/c29d14b4698b40e3b0d21efe50124d96.png
[format_png 6]: /images/20221123/f13afce737ed40978d39d5d7a20ed857.png
[format_png 7]: /images/20221123/ddd8f784c7fb4d09ab481cbb8200403c.png
[format_png 8]: /images/20221123/e18a102fcc2b4f0b8ba8067dd34fa096.png
[format_png 9]: /images/20221123/2b2747c55a19433a9e94a155a0dae8f1.png
[LeetCode]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e75efcd79fcf9c65ebb5070122b9705e18cb1c46b06c5eb3e299520ed4a25e327bc07bb4b&idx=2&mid=2247490158&scene=21&sn=12e587a361f0df072d2dc164c219a61e#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e75aecd79fcb8b5f932c7ba5ed7a9e34a6c99f20bc129cef33774167d668e8745755d02ad&idx=1&mid=2247490095&scene=21&sn=baa0379b1ca62db17327a2cb825a1b24#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0d87aacd7a0ebc3ada34a076d1fa3943ee24097966257132b1042b7a3e4debedc78f38c8cf&idx=1&mid=2247493675&scene=21&sn=6b501ef2032ab911f0a3519eb7397017#wechat_redirect
[MySQL _ B_]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e759ccd79fc8a73c77eacfd7c8b1391b08864e2e13fdf5a6e41e218a499d5a87ee12e4e6a&idx=2&mid=2247490077&scene=21&sn=56c52b385c98c7f0ad33c2621da101eb#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e767dcd79ff6b2733dd8905f188afb19eb400d5e644f5b5127f909ee7c3583786031f9c20&idx=2&mid=2247490044&scene=21&sn=bb3610dfedbb2e0c017c3ff3d5e4684b#wechat_redirect
[format_png 10]: /images/20221123/7b2bdb083f64425ea53bdd3f15345372.png