链表中多个子链表的翻转

25.题目链接-来源:力扣(LeetCode)

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

进阶:

你可以设计一个只使用常数额外空间的算法来解决此问题吗?
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

示例 1:

输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]

思路:

此题是上一题的一般情况,我们可以沿用其框架,即对于一段长度为 k 的待处理节点,用 preCur 指向该段的前驱,用 curFront 标记本段的起始节点,然后对 preCur 之后的 k 个节点,我们提取一个 reverse() 方法单独处理对其的翻转操作,返回反转以后的头结点。由于我们要避免处理长度不足 k 的末尾段,在进行 reverse() 操作之前,我们要从 preCur 之后数出 k 个节点,若计数未满即至表尾,则表示已经无需操作,跳出循环。
每次循环末尾,我们需要更新 preCur 的信息,preCur 作为下一段节点的前驱,其应该指向当前段完成 reverse() 以后的最末节点,也就是本轮循环一开始的起始节点 curFront。
记得用 哑节点 dummy 帮助我们简化判断逻辑,完成后,返回 dummy.next即可。
时间复杂度:O(n)
空间复杂度:O(1)

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0, head);
ListNode preCur = dummy, curFront = preCur.next;
PROC:
while (curFront != null) {
ListNode curEnd = curFront;
for (int i = 1; i < k; i++) {
curEnd = curEnd.next;
if (curEnd == null) {
break PROC;
}
}
preCur.next = reverse(curFront, k);

preCur = curFront;
curFront = curFront.next;
}
return dummy.next;
}
private ListNode reverse(ListNode head, int k) {
ListNode cur = head, pre = null;
while (k > 0) {
ListNode rest = cur.next;
cur.next = pre;
pre = cur;
cur = rest;
k--;
}
head.next = cur;
return pre;
}
}