反转偶数长度组的节点
难度:
标签:
题目描述
给你一个链表的头节点 head 。
链表中的节点 按顺序 划分成若干 非空 组，这些非空组的长度构成一个自然数序列（1, 2, 3, 4, ...）。一个组的 长度 就是组中分配到的节点数目。换句话说：
- 节点
1分配给第一组 - 节点
2和3分配给第二组 - 节点
4、5和6分配给第三组，以此类推
注意，最后一组的长度可能小于或者等于 1 + 倒数第二组的长度 。
反转 每个 偶数 长度组中的节点，并返回修改后链表的头节点 head 。
示例 1：
输入：head = [5,2,6,3,9,1,7,3,8,4] 输出：[5,6,2,3,9,1,4,8,3,7] 解释： - 第一组长度为 1 ，奇数，没有发生反转。 - 第二组长度为 2 ，偶数，节点反转。 - 第三组长度为 3 ，奇数，没有发生反转。 - 最后一组长度为 4 ，偶数，节点反转。
示例 2：
输入：head = [1,1,0,6] 输出：[1,0,1,6] 解释： - 第一组长度为 1 ，没有发生反转。 - 第二组长度为 2 ，节点反转。 - 最后一组长度为 1 ，没有发生反转。
示例 3：
输入：head = [2,1] 输出：[2,1] 解释： - 第一组长度为 1 ，没有发生反转。 - 最后一组长度为 1 ，没有发生反转。
提示：
- 链表中节点数目范围是
[1, 105] 0 <= Node.val <= 105
代码结果
运行时间: 563 ms, 内存: 37.8 MB
// Java Stream Solution
// 思路: 使用stream处理链表的序列化和反序列化，确保在反转偶数组时灵活处理
import java.util.*;
import java.util.stream.*;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode reverseEvenLengthGroups(ListNode head) {
if (head == null) return null;
List<Integer> values = new ArrayList<>();
ListNode current = head;
while (current != null) {
values.add(current.val);
current = current.next;
}
List<Integer> result = new ArrayList<>();
int start = 0, groupSize = 1;
while (start < values.size()) {
int end = Math.min(start + groupSize, values.size());
List<Integer> group = values.subList(start, end);
if (group.size() % 2 == 0) {
Collections.reverse(group);
}
result.addAll(group);
start = end;
groupSize++;
}
ListNode dummy = new ListNode(0);
current = dummy;
for (int val : result) {
current.next = new ListNode(val);
current = current.next;
}
return dummy.next;
}
}
解释
方法:
题解的主要思路是使用一个循环遍历链表，根据每个组的长度对偶数长度的组进行反转。首先，使用一个指针`pre_group_last`来标记每个组的最后一个节点。在循环中，首先确定当前组的长度并找到下一组的起始节点`next_group_first`。如果当前组的长度是偶数，就在`cur`和`pre_group_last.next`之间进行反转。循环每次处理一个组，直到链表尾部。反转过程中，使用的是经典的链表节点反转技术。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在算法中，如何准确地确定每个组的长度并且正确地标记每组的最后一个节点？
▷🦆
在处理最后一组时，算法是如何判断它的长度可能小于或等于1+倒数第二组的长度，并作出相应的处理决策的？
▷🦆
在反转偶数长度组的节点时，算法使用的链表反转技术是否有可能导致链表的断裂，尤其是在连接下一组的起始节点时？
▷🦆
考虑到算法变量`group_num`的计算方式，是否存在可能因为循环中断提前而导致`group_num`计数不准确的情况？
▷