链表K个节点的组内逆序调整问题
作者：Grey
原文地址：
题目描述
LeetCode 25. Reverse Nodes in k-Group
本题的 follow up 是：
Follow-up: Can you solve the problem in O(1) extra memory space?
即用\(O(1)\)的空间复杂度实现整个算法。
主要思路
本题需要设计两个方法：
第一个方法
ListNode getKGroupEnd(ListNode start, int k)
该方法表示：从链表start位置开始，数够k个位置，返回k个位置后的那个节点。
比如链表为：
...-> start -> b -> c -> d -> e
假设：k = 3，
则：表示从start开始，数够 3 个，所以返回c节点
如果是下述情况
...-> start -> b -> c -> null
假设：k = 6，
由于start后面不够 6 个节点，所以返回null，完整代码如下：
public static ListNode getKGroupEnd(ListNode start, int k) {
while (--k != 0 && start != null) {
start = start.next;
}
return start;
}
第二个方法void reverse(ListNode start, ListNode end)，表示反转start到end之间的链表。
例如：原链表为：
....->a->b->c->d->e....
假设：start = a, end = d
经过reverse方法，会变成
...d->c->b->a->e.....
reverse方法也相对比较简单，就是链表反转的一种特殊情况，实现代码如下:
public static void reverse(ListNode start, ListNode end) {
end = end.next;
ListNode pre = null;
ListNode cur = start;
while (cur != end) {
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
start.next = end;
}
有了上述两个方法，我们可以比较方便实现原题要求，主流程如下
public static ListNode reverseKGroup(ListNode head, int k) {
ListNode start = head;
ListNode end = getKGroupEnd(start, k);
if (end == null) {
return head;
}
// 第一组凑齐了！
head = end;
reverse(start, end);
// 上一组的结尾节点
ListNode lastEnd = start;
while (lastEnd.next != null) {
start = lastEnd.next;
end = getKGroupEnd(start, k);
if (end == null) {
return head;
}
reverse(start, end);
lastEnd.next = end;
lastEnd = start;
}
return head;
}
整个过程时间复杂度\(O(N)\)，空间复杂度\(O(1)\)。