社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
前几天有个小伙伴去面试字节跳动，面试官问了他一道链表相关的算法题，不过他一时之间没做出来，就来问了我一下，感觉这道题还不错，拿来讲一讲。
这其实是一道变形的链表反转题，大致描述如下：
给定一个单链表的头节点 head，实现一个调整单链表的函数，使得每K个节点之间为一组进行逆序，并且从链表的尾部开始组起，头部剩余节点数量不够一组的不需要逆序。(不能使用队列或者栈作为辅助)。
例如：
这道题的难点在于，是从链表的尾部开始组起的，而不是从链表的头部，如果是头部的话，那我们还是比较容易做的，因为你可以遍历链表，每遍历 k 个就拆分为一组来逆序。但是从尾部的话就不一样了，因为是单链表，不能往后遍历组起，不过这道题肯定是用递归比较好做。
先做一道类似的反转题
在做这道题之前，我们不仿先来看看如果从头部开始组起的话，应该怎么做呢?例如：链表: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。
我们把前K个节点与后面的节点分割出来：
temp指向的剩余的链表，可以说是原问题的一个子问题。我们可以调用reverseKNode()方法将temp指向的链表每K个节点之间进行逆序。再调用reverse()方法把head指向的那3个节点进行逆序，结果如下：
接着，我们只需要把这两部分给连接起来就可以了。最后的结果如下：
代码如下：
回到本题
这两道题可以说是及其相似的了，只是一道从头部开始组起，这道从头部开始组起的，也是 leetcode 的第 25 题。而面试的时候，经常会进行变形，例如这道字节跳动的题，它变成从尾部开始组起，可能你一时之间就不知道该怎么弄了。当然，可能有人一下子就反应出来，把他秒杀了。
其实这道题很好做滴，你只需要先把单链表进行一次逆序，逆序之后就能转化为从头部开始组起了，然后按照我上面的解法，处理完之后，把结果再次逆序即搞定。两次逆序相当于没逆序。
例如对于链表(其中 K = 3)
我们把它从尾部开始组起，每 K 个节点为一组进行逆序。步骤如下：
① 先进行逆序
逆序之后就可以把问题转化为从头部开始组起，每 K 个节点为一组进行逆序。
② 处理后的结果如下：
③ 接着在把结果逆序一次，结果如下：
代码如下：
类似于这种需要先进行逆序的还要两个链表相加，这道题字节跳动的笔试题也有出过，如下图的第二题：
这道题就需要先把两个链表逆序，再节点间相加，最后在合并了。
关于链表的算法题，在面试的时候听说是挺常考的，大家可以多注意注意。如果你觉得这篇内容对你挺有启发，那就点个赞呗~
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
