【链表问题】打卡9：将单链表的每K个节点之间逆序

前言

以专题的形式更新刷题贴，欢迎跟我一起学习刷题，相信我，你的坚持，绝对会有意想不到的收获。每道题会提供简单的解答，如果你有更优雅的做法，欢迎提供指点，谢谢。

注：如果代码排版出现了问题麻烦通知我下，谢谢。

【题目描述】

给定一个单链表的头节点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不调整，因为不够一组。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【难度】

尉：★★☆☆

【解答】

对于这道题，如果你不知道怎么逆序一个单链表，那么可以看一下我之前写的【链表问题】如何优雅着反转单链表

这道题我们可以用递归来实现，假设方法reverseKNode()的功能是将单链表的每K个节点之间逆序。reverse()方法的功能是将一个单链表逆序。

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

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

temp指向的剩余的链表，可以说是原问题的一个子问题。我们可以调用reverseKNode()方法将temp指向的链表每K个节点之间进行逆序。再调用reverse()方法把head指向的那3个节点进行逆序，结果如下：

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

如果不大理解，看下代码可能就比较好理解了。

代码如下

 1//每k个节点为一组的逆转
 2public static Node reverseKNodes(Node head, int k) {
 3    if (head == null || head.next == null) {
 4        return head;
 5    }
 6    Node cur = head;
 7    for (int i = 1; cur != null && i < k; i++) {
 8        cur = cur.next;
 9    }
10    //判断是否能组成一组。
11    if (cur == null) {
12        return head;
13    }
14    //temp指向剩余的链表
15    Node temp = cur.next;
16    cur.next = null;
17    //把k个节点进行反转
18    Node newHead = reverse(head);
19    //把之后的部分链表进行每K个节点逆转转
20    Node newTemp = reverseKNodes(temp, k);
21    //把两部分节点连接起来
22    return newHead;
23}
24
25    //单链表逆序
26public static Node reverse(Node head) {
27    if (head == null || head.next == null) {
28        return head;
29    }
30    Node newHead = reverse(head.next);
31    head.next.next =  head;
32    head.next = null;
33    return newHead;
34}

当然，这道题一个很简单的做法就是利用栈来辅助，每K个节点入栈就把这K个节点出栈连接成一个链表，之后剩余再在进栈…..

不过这种做法的额外空间复杂度是O(K)。

问题拓展

思考：如果这是一个环形单链表呢？该如何实现呢？

往期

为了方便寻找文章，我把文章目录整理了下，把文章导航放在了github上：https://github.com/iamshuaidi/writing