2074-反转偶数长度组的节点

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

给你一个链表的头节点 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

方法一：对每个组进行两次遍历

思路与算法

我们可以从链表的首节点开始进行遍历，并且使用一个计数器 i，它既表示当前遍历的组数，也表示当前的组最多能包含的节点个数。

记当前组的首节点为 cur，其前驱节点为 pre，那么我们可以当前组进行最多两次遍历：

  • 第一次遍历时，我们的目的是获取当前组包含的节点个数。我们从 cur 开始，遍历最多不超过 i 个节点，并记录遍历到的节点个数，记为 len。

  • 第二次遍历时，我们的目的是反转当前组包含的节点。如果 len 为偶数，那么我们就需要反转。具体的做法时，我们从 cur 的后继节点开始遍历，遍历恰好 len} - 1 个节点，每遍历到一个节点，就将该节点「插入」到 pre 的后面，这样就能实现对链表的反转，读者也可以参考「206. 反转链表」的官方题解 。

  • 第三次遍历时，我们的目的是将 cur 和 pre 移动到下一个组的首节点以及其前驱节点。如果我们执行了第二次遍历（len 为偶数），那么 cur 就从组的首节点变成了尾节点，即 cur 的后继节点就是下一个组的首节点，而 cur 本身就是下一个组的 pre。如果我们没有执行第二次遍历，那么就需要将 pre 和 cur 分别向后移动 len 个节点。

可以发现，如果 len 为偶数，那么只需要执行第一和二次遍历，如果 len 为奇数，那么只需要执行第一和第三次遍历。因此每一个组最多会被遍历两次。

当 cur 移动到空节点时，说明我们处理完了整个链表，此时就完成了遍历。

代码

[sol1-C++]
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
class Solution {
public:
    ListNode* reverseEvenLengthGroups(ListNode* head) {
        int i = 0;
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while (cur) {
            ++i;
            ListNode* it = cur;
            int len = 0;
            for (; len < i && it; ++len) {
                it = it->next;
            }
            
            if (len & 1) {
                for (int j = 1; j <= len; ++j) {
                    tie(pre, cur) = tuple{cur, cur->next};
                }
            }
            else {
                for (int j = 1; j < len; ++j) {
                    tie(pre->next, cur->next, cur->next->next) = tuple{cur->next, cur->next->next, pre->next};
                }
                tie(pre, cur) = tuple{cur, cur->next};
            }
        }
        return head;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        i = 0
        cur, pre = head, None
        while cur:
            i += 1
            it = cur
            length = 0
            while length < i and it:
                length += 1
                it = it.next
            
            if length & 1:
                for j in range(length):
                    pre, cur = cur, cur.next
            else:
                for j in range(length - 1):
                    pre.next, cur.next.next, cur.next = cur.next, pre.next, cur.next.next
                pre, cur = cur, cur.next

        return head

复杂度分析

  • 时间复杂度：O(n)，其中 n 是链表的长度。

  • 空间复杂度：O(1)。

 Comments
On this page
2074-反转偶数长度组的节点