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

雨点打透心脏的1/2处 2024-04-17 19:53 88阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | 帅地

来源公众号 | 苦逼的码农

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

### 题目 ###

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

给定一个单链表的头节点 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不调整，因为不够一组。

对于这道题，如果你不知道怎么逆序一个单链表，那么可以看一下我之前写的[如何优雅着反转单链表][Link 2]

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

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

![640?wx\_fmt=png][640_wx_fmt_png] 我们把前K个节点与后面的节点分割出来：

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

![640?wx\_fmt=png][640_wx_fmt_png 2]

> 再次声明，如果对这个递归看不大懂的，建议看下我那篇递归的文章

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

![640?wx\_fmt=png][640_wx_fmt_png 3]

代码如下：

//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）

![640?wx\_fmt=png][640_wx_fmt_png] 我们把它从尾部开始组起，每 K 个节点为一组进行逆序。 步骤如下

1、先进行逆序

![640?wx\_fmt=png][640_wx_fmt_png 4] 逆序之后就可以把问题转化为从 **头部**开始组起，每 K 个节点为一组进行逆序。

2、处理后的结果如下

![640?wx\_fmt=png][640_wx_fmt_png 5]

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

![640?wx\_fmt=png][640_wx_fmt_png 6]

代码如下

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

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

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

具体题解点这：[图解LeetCode第 2 号问题：两个数字相加][LeetCode_ 2]

![640?wx\_fmt=png][640_wx_fmt_png 7]

**热门推荐** ![640?wx\_fmt=gif][640_wx_fmt_gif]

1.【程序员】[全球最厉害的 14 位程序员][14]

2.【GitHub】[我在 GitHub 上看到了一个丧心病狂的开源项目！][GitHub]

3.【算法】[动画：七分钟理解什么是KMP算法][KMP]

4.【数据结构】[十大经典排序算法动画与解析，看我就够了][Link 3]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/8008a4df9b294b47afc22f7fdbbe6640.png
[Link 1]: https://mp.weixin.qq.com/s?__biz=Mzg2NzA4MTkxNQ==&mid=2247485092&idx=1&sn=ff44f169aa57cac8a8e6595b7ff49ab8&scene=21#wechat_redirect
[Link 2]: https://mp.weixin.qq.com/s?__biz=Mzg2NzA4MTkxNQ==&mid=2247485176&idx=2&sn=c2e38deadcdfa5bef677f47d0ef3d908&scene=21#wechat_redirect
[640_wx_fmt_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/ed03d80aecb04829a756b0e9a719b267.png
[640_wx_fmt_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/f1d16a0e53624e9fb274cb18aa7500b2.png
[640_wx_fmt_png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/0ace2962a4af4498a9d659ebb1e3308b.png
[640_wx_fmt_png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/b22a984c920a4dd7b24059c2d3c1faf3.png
[640_wx_fmt_png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/8685a9d8d77244f5bcb18d27e23b02b5.png
[640_wx_fmt_png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/b8cc0f3128cc4f8eb59b1a9b239cd4af.png
[640_wx_fmt_png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/40b19c708a034d41b66972e3ded12916.png
[640_wx_fmt_jpeg 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/8533b2513daa436cbb174a07dbf04ae6.png
[LeetCode_ 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484231&idx=2&sn=6a9eb4fd0619c822e4dede69b8d841c8&chksm=fa0e6cc6cd79e5d0c03fffcd65b665fed62db9dca9c97771898f388ea292ce806bfd6eb908b5&scene=21#wechat_redirect
[640_wx_fmt_png 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/e0ca2a4b99d84de1861603ce2ba50a04.png
[640_wx_fmt_gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/e8781ded053144b7bbfe5319f4d04dae.gif
[14]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486099&idx=1&sn=6ea84944fe6a3d6dd1af2b00f3e53002&chksm=fa0e6512cd79ec04c8e8c63e74d78cc23629b88290a8e0642e5e44601f99fc39a3ea530867bc&scene=21#wechat_redirect
[GitHub]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486254&idx=1&sn=654c208601879fe1b76c682a069a4e6a&chksm=fa0e64afcd79edb960a9863c7af7e6de5893da2326e6eca2bcd9d68061966d200ba0e189ab91&scene=21#wechat_redirect
[KMP]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485939&idx=1&sn=b25f39b5644da92c4047bbbd9936f73c&chksm=fa0e6672cd79ef64dda0a21e23c2817edf4a64cbb75b9bed328d6519c6cd4fef36d03a4cb309&scene=21#wechat_redirect
[Link 3]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[640_wx_fmt_jpeg 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/fc9e8348eea140ac875f167215435a05.png