leetcode链表之反转偶数长度组的结点

2074、反转偶数长度组的结点

题目：

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

示例2：

输入：head = [1,1,0,6]
输出：[1,0,1,6]

示例3：

输入：head = [2,1]
输出：[2,1]

示例4：

输入：head = [8]
输出：[8]

class Solution:
    # 反转从left到right结点的链表
    def reversed(self, left, right):
        prev, cur = None, left
        while cur != right:
            next = cur.next
            cur.next = prev
            prev = cur
            cur = next
        return prev, left
        pass

    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = vHead = ListNode(0, head)
        # 记录分组的长度
        timeLength = 1
        prev = None
        while cur:
            # 通过curLength是否是偶数来判断是否需要进行反转
            curLength = timeLength
            for i in range(timeLength):
                cur = cur.next
                # 最后一组的长度可能小于分组长度，这里由于下标从0开始，所以长度应该是i+1
                if not cur.next:
                    curLength = i + 1
                    break
            # 如果是偶数，对链表进行反转
            if curLength and curLength % 2 == 0:
                # 由于创建里虚拟头结点，所以prev和cur记录的都是当前组头结点的前置结点和尾结点
                # 如果要反转，next要传尾结点的下一节点
                next = cur.next
                left, right = self.reversed(prev.next, next)
                prev.next = left
                right.next = next
                cur = right
            # 由于for循环提前退出，这里可以判断结点是否满足退出环境，进行while循环的退出
            if not cur or not cur.next:
                break
            prev = cur
            timeLength += 1
        return vHead.next