一道字节跳动的算法面试题，你能做出来吗？

最近有个朋友来面试字节跳动

01 题目

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

给定单链表的头指针head，请设计并实现一个函数用于调整单链表结构。该函数将按如下规则对链表进行处理：将每连续K个节点划分为一组，并对每一组进行逆序处理；若这些分组是从链表末尾开始划分，则最后一组可能包含少于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不调整，因为不够一组。

02 解答

解决这道题的关键在于其特殊的分组方式——是基于链表尾部分组完成而非从头节点分组开始。如果基于头节点分组的话，则相对容易实现——通过逐个节点遍历可以将每k个节点组成一组并逆序排列。然而，在这种情况下（即基于尾部分组的方式），由于单链表的限制无法向后移动——而这类问题通常推荐使用递归的方法来解决。

先做一道类似的反转题

在解答这道题之前

这道题我们可以采用递归方法来解决；假设method reverseKNode()的作用是对单链表每隔K个节点进行逆序排列（从开头开始分组哦）; reverse()函数的作用是对单链表进行逆序排列。

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

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

该链表可以看作是原问题的一个子问题。通过调用reverseKNode()方法可以实现对该链表中每K个节点之间的逆序处理。接着使用reverse()方法对该部分三个节点进行逆序处理。

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

代码如下：

回到本题

可以说这两道题目极其相似；其中一道则是从头部开始组起；这也正是 LeetCode 上第 25 题；而在面试中经常会出现变体；比如这道来自字节跳动的题；它的变体则会从尾部开始组成；这样你可能会一时难以找到解决办法；当然有人很快就反应过来并轻松解决它。

其实这道题并不难。你只需要将单链表进行一次操作——使其倒转——随后就能够以原有头部开始分组。接着按照我之前的方法处理完毕后即可完成任务。两次倒转的效果等同于未进行任何操作。

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

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

① 先进行逆序

逆序操作完成后即可将问题转化为从最前端部分开始分组，并按每K个节点组成一组执行逆序处理。

② 处理后的结果如下

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

代码如下

比如，在进行逆序操作时，还需要对两个链表进行求和运算。这道题曾在字节跳动的笔试中出现过，请参考下图中的问题描述为第二题

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

03 总结

在面试中常见的是关于链表的算法题。建议大家多多关注关注。如果你认为这篇内容对你很有帮助，请别忘了点赞。