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

Difficulty
Medium
Tags
链表
URL
https://leetcode.cn/problems/reverse-nodes-in-even-length-groups/
Star
给你一个链表的头节点 head 。
链表中的节点 按顺序 划分成若干 非空 组，这些非空组的长度构成一个自然数序列（1, 2, 3, 4, ...）。一个组的 长度 就是组中分配到的节点数目。换句话说：
  • 节点 1 分配给第一组
  • 节点 2 和 3 分配给第二组
  • 节点 4、5 和 6 分配给第三组，以此类推
注意，最后一组的长度可能小于或者等于 1 + 倒数第二组的长度 。
反转 每个 偶数 长度组中的节点，并返回修改后链表的头节点 head 。
示例 1：
notion imagenotion image
输入：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

## 法 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]:
        groups = []
        groups_len = []
        prev = head
        cur = head 

        count = 1
        cur_length = 1

        while cur:
            if count == cur_length:
                groups.append(prev)
                groups_len.append(count)
                # 开始下一组
                nxt = cur.next
                if nxt:
                    cur.next = None

                    count = 1
                    cur_length += 1

                    prev = nxt
                    cur = nxt
                else:
                    break
            
            cur = cur.next
            count += 1
        # 最后一组别忘了
        if groups[-1] is not prev:
            groups.append(prev)
            groups_len.append(count-1)
        
        # self.print_groups(groups, groups_len)
        

        # 翻转该翻转的组
        for i, g in enumerate(groups):
            if i < len(groups)-1 and i % 2 == 1:
                groups[i] = self.reverse(g)
            elif i == len(groups) - 1 and groups_len[i] % 2 == 0:
                groups[i] = self.reverse(g)

        # self.print_groups(groups, groups_len)

        # 合并
        res = groups[0]
        tail = groups[0]
        for i in range(1, len(groups)):
            cur_list = groups[i]
            tail.next = cur_list
            
            while cur_list and cur_list.next:
                cur_list = cur_list.next
            tail = cur_list
        
        return res
                        
    
    def reverse(self, node):
        if node is None or node.next is None:
            return node
        
        prev, cur = None, node
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        
        return prev

    # 测试用
    def print_groups(self, groups, groups_len):
        for g in groups:
            temp = []
            cur = g
            while cur:
                temp.append(cur.val)
                cur = cur.next
            print(temp,end=" ")
        print("  len: ", groups_len)