前几天，有朋友去字节跳动面试。面试官问了他一道链表相关的算法题，他一时没解出来，就来问我了。我觉得这个问题还不错，让我们来谈谈它。01题目这其实是一个变形链表的倒置问题，大致描述如下：给定一个单向链表的头节点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没有调整，因为不够一组。02这道题的难点在于它是从链表尾部组装的，不是从链表头组装的。如果是头部，那我们做起来就比较容易了，因为你可以遍历链表。一个被分成一组以颠倒顺序。但是和最后不一样，因为是单链表，不能反向遍历组，但是这道题一定要用递归做比较好。先做一道类似的反转题。在做这道题之前，我们先看看如果从头开始做的话。例如：链表：1->2->3->4->5->6->7->8->null，K=3。调整后：3->2->1->6->5->4->7->8->空。其中7和8没有调整，因为不够一组。我们可以用递归来实现这道题，假设方法reverseKNode()的作用是将单向链表的每个K节点的顺序倒转（从头开始）；reverse()方法的作用是将单个链表的顺序倒序。那么对于下面的单向链表，其中K=3。我们将前K个节点与后面的节点分开：temp指向的剩余链表可以说是原问题的一个子问题。我们可以调用reverseKNode()方法来反转temp指向的链表中每K个节点的顺序。然后调用reverse()方法将head指向的三个节点的顺序倒过来，结果如下：接下来我们只需要将两部分连接起来即可。最终结果如下：代码如下：回到这道题，这两道题可以说是极其相似了，只不过一道是从头拼装，这道是从头拼装，也就是leetcode第25题。面试的时候经常会出现变形，比如这个字节跳动的问题，从最后变成了分组，你可能一时不知道怎么做。当然，也可能有人会第一时间反应过来，直接杀了他。其实这道题很容易做。你只需要先将单向链表的顺序倒转即可。完毕。两次反转相当于没有反转。例如，对于链表（其中K=3），我们从末尾开始对其进行分组，并将每K个节点倒序为一组。步骤如下：①先进行逆序后，可以将问题转化为一个从头开始的组，每K个节点为一组逆序。②处理后结果如下：③然后对结果进行一次反转，结果如下：代码如下：类似这种需要先反转顺序，需要添加两个链表，而这个题目写了字节跳动的试题，下图第二题：这道题需要先把两个链表的顺序倒过来，然后添加节点，最后合并。03总结一下链表的算法题。我听说他们在面试中经常被测试。你可以多加注意。如果你觉得这篇内容对你很有启发，那就点个赞吧~
