反转偶数长度组的节点

标签: 链表

难度: Medium

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

Submission

运行时间: 563 ms

内存: 37.8 MB

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre_group_last = head
        index = 1
        while pre_group_last:
            next_group_first = pre_group_last
            group_num = 0
            for i in range(index * 2 + 1):
                if not next_group_first:
                    break
                next_group_first = next_group_first.next
                group_num = i

            if not next_group_first and group_num % 2 == 1:
                break

            cur = pre_group_last.next
            void_head = cur
            pre_group_last.next = next_group_first
            while cur and cur != next_group_first:
                pre = cur
                cur = cur.next
                pre.next = pre_group_last.next
                pre_group_last.next = pre
            
            if not next_group_first:
                break

            group_num = 0
            next_pre_group_last = next_group_first
            for i in range(index * 2):
                if not next_pre_group_last:
                    break
                next_pre_group_last = next_pre_group_last.next
                group_num = i + 1

            if not next_pre_group_last:
                if group_num % 2 == 1:
                    break
                else:
                    cur = void_head.next
                    void_head.next = None
                    while cur:
                        pre = cur
                        cur = cur.next
                        pre.next = void_head.next
                        void_head.next = pre
            pre_group_last = next_pre_group_last
            index += 1
        return head

Explain

题解的主要思路是使用一个循环遍历链表，根据每个组的长度对偶数长度的组进行反转。首先，使用一个指针`pre_group_last`来标记每个组的最后一个节点。在循环中，首先确定当前组的长度并找到下一组的起始节点`next_group_first`。如果当前组的长度是偶数，就在`cur`和`pre_group_last.next`之间进行反转。循环每次处理一个组，直到链表尾部。反转过程中，使用的是经典的链表节点反转技术。

时间复杂度: O(n)

空间复杂度: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre_group_last = head  # 指向当前处理组的最后一个节点
        index = 1  # 当前组的序号
        while pre_group_last:  # 遍历所有组
            next_group_first = pre_group_last
            group_num = 0
            # 确定下一组的起始节点和当前组的长度
            for i in range(index * 2 + 1):
                if not next_group_first:
                    break
                next_group_first = next_group_first.next
                group_num = i

            # 如果最后一组长度为奇数，终止反转
            if not next_group_first and group_num % 2 == 1:
                break

            cur = pre_group_last.next  # 当前组的第一个节点
            void_head = cur  # 临时节点，用于反转操作
            pre_group_last.next = next_group_first  # 连接到下一组的起始
            # 反转当前组的节点
            while cur and cur != next_group_first:
                pre = cur
                cur = cur.next
                pre.next = pre_group_last.next
                pre_group_last.next = pre

            # 准备下一组的处理
            if not next_group_first:
                break

            group_num = 0
            next_pre_group_last = next_group_first
            for i in range(index * 2):
                if not next_pre_group_last:
                    break
                next_pre_group_last = next_pre_group_last.next
                group_num = i + 1

            # 处理倒数第二组情况
            if not next_pre_group_last:
                if group_num % 2 == 1:
                    break
                else:
                    cur = void_head.next
                    void_head.next = None
                    while cur:
                        pre = cur
                        cur = cur.next
                        pre.next = void_head.next
                        void_head.next = pre
            pre_group_last = next_pre_group_last
            index += 1
        return head

Explore

在算法中，通过使用一个循环来遍历节点，同时计数以确定每个组的长度。循环内部，`for i in range(index * 2 + 1)`尝试移动`next_group_first`指针，逐个访问节点直到到达指定的最大长度或链表结束。每次循环迭代，`i`增加，当循环退出时，`i`的值减1就是当前组的长度。此外，每组的最后一个节点是循环中最后一个被`next_group_first`访问的节点，因此可以通过`pre_group_last.next`来标记每组的开始，从而确定每组的结束位置。

在处理最后一组时，算法首先检查`next_group_first`是否为`None`，这表示已到达链表末尾。接着，通过检查`group_num`的值（在之前的循环中计算得到），来确定组的长度。如果`group_num`是奇数，算法将不执行反转，并直接终止，因为奇数长度的组不需要反转。如果是偶数，还需要考虑是否需要进行反转。此时，用已保存的节点连接信息来保证链表的完整性。

在链表反转过程中，确实需要小心处理节点的连接关系，以避免链表断裂。算法在开始反转前，将`pre_group_last.next`设置为`next_group_first`，这样在反转过程中，每次将当前节点`cur`移到`pre_group_last.next`的位置，可以确保链表的连贯性。这种方法确保了在反转节点时，新的节点连接不会丢失，从而避免了链表断裂的问题。

是的，存在这种可能性。`group_num`的值依赖于循环的迭代次数，如果链表在达到预计的组长度之前就结束了，`group_num`将小于预期。这可以通过检查`next_group_first`是否为`None`来管理。如果`next_group_first`在达到预定迭代次数之前为`None`，表示链表已经结束，此时`group_num`的结果即为实际的组长度。这种情况需要正确处理以确保链表的正确操作和逻辑判断的准确性。