链表训练8：将单链表的每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个节点进行逆序，结果如下：
接着，我们只需要把这两部分给连接起来就可以了。最后的结果如下：
如果不大理解，看下代码可能就比较好理解了。
代码如下
//每k个节点为一组的逆转
public static Node reverseKNodes(Node head, int k) {
if (head == null || head.next == null) {
return head;
}
Node cur = head;
for (int i = 1; cur != null && i < k; i++) {
cur = cur.next;
}
//判断是否能组成一组。
if (cur == null) {
return head;
}
//temp指向剩余的链表
Node temp = cur.next;
cur.next = null;
//把k个节点进行反转
Node newHead = reverse(head);
//把之后的部分链表进行每K个节点逆转转
Node newTemp = reverseKNodes(temp, k);
//把两部分节点连接起来
return newHead;
}
//单链表逆序
public static Node reverse(Node head) {
if (head == null || head.next == null) {
return head;
}
Node newHead = reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}当然，这道题一个很简单的做法就是利用栈来辅助，每K个节点入栈就把这K个节点出栈连接成一个链表，之后剩余再在进栈.....
不过这种做法的额外空间复杂度是O(K)。
问题拓展
思考：如果这是一个环形单链表呢？该如何实现呢？
如果喜欢本网站{https://www.iamshuaidi.com), 那么可以把该网站分享给其他人，帅地正在疯狂更新中….