罕见的链表翻转,字节跳动加了个前提,口试者高呼「我太难了」| 图解算法
2019-11-18杂谈搜奇网52°c
A+ A-本文首发自民众号「承香墨影(ID:cxmyDev)」,迎接关注。
一. 序
我又来讲链表题了,这道题听说是来自字节跳动的口试题。
为何说是「听说」呢?由于我也是看来的,以为题目照样挺有意义,然则原作者给出的计划,我想了想以为另有优化空间,就零丁拿出来讲讲。
就像本文的题目说的,这是一道关于链表翻转的题。链表的翻转,之前的文章也讲了许多,比方:链表翻转、链表两两翻转、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 个一组翻转链表》。
三. 小结时候
以上就是我解这道题的思绪,能够不是最高效的,但也算是比较清楚。
在口试历程当中,链表相干的题目能够说是高频题。虽然企业在出题时,为了增添难度也会做一些变种,然则作为口试者,无论如何都避不开多练多写多想。
你有更好的计划吗?你在口试中有遇到什么奇葩的算法题吗?迎接在留言区议论。
本文对你有协助吗?留言、转发、珍藏是最大的支撑,感谢!
民众号背景复兴生长『生长』,将会获得我预备的进修材料,也能复兴『加群』,一同进修提高。