一. 序
我又来讲链表题了, 这道题据说是来自字节跳动的面试题.
为什么说是「据说」呢? 因为我也是看来的, 觉得题目还是挺有意思, 但是原作者给出的方案, 我想了想觉得还有优化空间, 就单独拿出来讲讲.
就像本文的题目说的, 这是一道关于链表翻转的题. 链表的翻转, 之前的文章也讲了很多, 例如: 链表翻转, 链表两两翻转 ,K 个一组翻转链表. 这些其实都是 leetcode 上的标准题, 但是通常企业给出的面试题, 多半会做一些变种, 也就是加一些特殊的条件.
例如今天要讲的这道题.
给定单链表的头结点 head, 实现一个调整链表的函数, 从链表尾部开始, 以 K 个结点为一组进行逆序翻转, 头部剩余结点不足一组时, 不需要翻转.(不能使用队列或者栈作为辅助)
仔细读题, 像不像我们之前讲到的 leetcode 第 25 题: K 个一组翻转链表 .
leetcode-25 是从头结点开始, 以 K 个结点一组进行翻转. 而字节跳动这道题, 是从尾结点开始.
只是多了一个从尾结点开始分组翻转的条件, 这道题的难度就增加了.
二. K 个一组翻转链表 (头条版)
2.1 其他人的解题思路
前面也说到, 这道题是我看来的, 当时是以一篇文章的形式发布出来.
文章我就不发了, 不过先了解一下他的解题思路, 有助于我们思考.
他的思路很清晰, 虽然这道题他不会解, 但是 leetcode-25 这个标准的以 K 个一组翻转链表的题他很熟悉.
那么可以先将原始链表, 进行一次「链表翻转」, 再进行「K 个一组翻转链表」, 最后再做一次「链表翻转」还原链表, 就得出了需要的结果.
- ListNode revserseKGroupPlus(ListNode head, int k) {
- // 翻转链表
- head = reverseList(head);
- // K 个一组翻转链表
- head = reverseKGroup(head, k);
- // 翻转链表
- head = reverseList(head);
- return head;
- }
把一个不熟悉的问题, 经过简单的转换, 变成熟悉的问题进行解决, 这种思路是没有错的.
但是呢, 有个问题 --
在面试的场景中, 通常来说, 面试官的水平会高于面试者, 那么我们可以简单的理解, 面试就是一个不断受挫的过程, 这个过程总会被问到我们知识的边界才会停止.
面试题只是起点, 面试过程中深挖的那些问题, 才是触摸到我们谈薪资本的核心. 当然这扯远了, 继续回到本文的内容.
此时就算面试者当场写出了解题代码, 也逃不开一个经典问题.
面试官:「 还有更优的方案吗? 」
那么这道题, 有没有更优的方案? 答案当然是有的.
2.2 更优一点的方案
将链表先翻转后处理, 再翻转回去, 这样并不优雅, 其实只需一次以 K 个一组翻转链表就可以.
再回忆一下 leetcode 第 25 题, 它和这道题的差异, 主要来自于, 对不足一组的链表结点的处理. leetcode-25 是从头结点开始处理, 所以多出来的结点会在尾部, 而字节跳动这道题则正好相反, 余下的结点会在头部.
但是它们同时也有一种特殊情况, 就是 K 个一组进行分组时, 这里的 K 正好可以完整的分组, 一个不多, 一个不少的分成 N 组.
当链表结点数量正好为 K * N 时, 那么就又回到了我们熟悉的 leetcode-25 题了.
如果我们先将原始结点进行处理, 找出它正好可以整除 K 的起始结点 offset, 将这个起始结点 offset 的子链表, 进行 K 个一组进行翻转链表, 最后把它拼接回原始链表, 就完成了这道题.
这个过程, 需要额外定义两个结点, 第一个满足 K 个分组条件的 offset 结点 , 以及 offset 的前驱结点 prev 结点 ,prev 结点主要是用来拼接翻转后的两个链表, 让其不会出现链表断裂的问题.
它们的关系如下:
这其中还涉及到一些简单的链表运算, 例如求链表的长度, 这里就不展开说了, 直接上核心代码, 逻辑都在注释里, 我们先定义一个 reverseKGroupPlus() 方法.
public ListNode reverseKGroupPlus(ListNode head, int k) { if (head == null || k <= 1) return head; // 计算原始链表长度 int length = linkedLength(head); if (length <k) return head; // 计算 offset int offsetIndex = length % k; // 原始链表正好可以由 K 分为 N 组, 可直接处理 if (offsetIndex == 0) { return reverseKGroup(head, k); } // 定义并找到 prev 和 offset ListNode prev = head, offset = head; while (offsetIndex> 0) { prev = offset; offset = offset.next; offsetIndex--; } // 将 offset 结点为起始的子链表进行翻转, 再拼接回主链表 prev.next = reverseKGroup(offset, k); return head; }
注意当链表长度正好可以用 K 分为 N 组时, 我们直接处理, 否者才需要后续复杂的逻辑.
代码的注释足够清晰了, 在脑子里过一遍代码的执行流程应该能明白, 为了帮助大家理解, 我又画了个示意图.
假设以 head 为头结点的链表长度是 10,K 为 4 时, 那么计算下来 offset Index 就是 2.
找到 prev 和 offset 结点后, 就可以将以 offset 结点为头结点的子链表, 进行 K 个一组翻转链表的操作了.
此时, head 结点为起始的链表, 就是我们计算后的结果.
2.3 再补一些额外的代码
这道题, 还涉及到很多其他的小算法, 本身 leetcode-25 就已经被定级为「困难」, 字节跳动在这道题的基础上, 又增加了难度.
为了保证解题的完整, 这里再补充一些相关代码.
1. 计算链表长度
private int linkedLength(ListNode head) { int count = 0; while (head != null) { count++; head = head.next; } return count; }
没什么好说的, 一个 while 循环搞定.
2. 以 K 个一组翻转链表
这道题在之前的文章中详细讲解了, 这里直接贴代码了.
public ListNode reverseKGroup(ListNode head, int k) { // 增加虚拟头结点 ListNode dummy = new ListNode(0); dummy.next = head; // 定义 prev 和 end 结点 ListNode prev = dummy; ListNode end = dummy; while(end.next != null) { // 以 k 个结点为条件, 分组子链表 for (int i = 0; i < k && end != null; i++) end = end.next; // 不足 K 个时不处理 if (end == null) break; // 处理子链表 ListNode start = prev.next; ListNode next = end.next; end.next = null; // 翻转子链表 prev.next = reverseList(start); // 将子连表前后串起来 start.next = next; prev = start; end = prev; } return dummy.next; } // 递归完成单链表翻转 private ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode p = reverseList(head.next); head.next.next = head; head.next = null; return p; }
对于 leetcode-25 这道题, 还不太了解的可以看看之前的文章《K 个一组翻转链表》.
三. 小结时刻
以上就是我解这道题的思路, 可能不是最高效的, 但也算是比较清晰.
在面试过程中, 链表相关的题目可以说是高频题. 虽然企业在出题时, 为了增加难度也会做一些变种, 但是作为面试者, 无论如何都避不开多练多写多想.
你有更好的方案吗? 你在面试中有碰到什么奇葩的算法题吗? 欢迎在留言区讨论.
本文对你有帮助吗? 留言, 转发, 点好看 是最大的支持, 谢谢!
「 联机圆桌 」:point_left: 推荐我的知识星球, 一年 50 个优质问题, 上桌联机学习.
公众号后台回复成长『 成长 』, 将会得到我准备的学习资料, 也能回复『 加群 』, 一起学习进步.
来源: http://www.tuicool.com/articles/3Iza6bn